本地AC,但是提交上去却全RE了???
查看原帖
本地AC,但是提交上去却全RE了???
175011
rfsfreffr楼主2022/8/16 14:14

怀疑宏定义的问题?

#include<bits/stdc++.h>
#define get(u,v,w,id) int v=b[u][i].to,w=b[u][i].w,id=b[u][i].id;
using namespace std;

const int N=2e5+5;
const int M=1e6+5;

struct oi{
	int to;
	int w;
	int id;
};

int n,kk;
vector<oi> b[N];
int vis[N];
int siz[N];
int sz;
int minn;
int new_rt;
int is[M];
int ans=2e9;

void read() {
	cin>>n>>kk;
	for(int i=1; i<=n-1; i++) {
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		u++;
		v++;
		b[u].push_back({v,w,i});
		b[v].push_back({u,w,i});
	}
}

void dfs(int u,int fa) {//find_core 与 get_size 的核心部分
	siz[u]=1;
	int maxn=0;
	for(int i=0; i<b[u].size(); i++) {
		get(u,v,w,id);
		if(v==fa||vis[id]) continue ;
		dfs(v,u);
		siz[u]+=siz[v];
		if(siz[v]>maxn) maxn=siz[v];
	}
	maxn=max(maxn,sz-siz[u]);
	if(maxn<minn) {
		minn=maxn;
		new_rt=u;
	}
}

int get_size(int root) {
	dfs(root,0);
	sz=siz[root];
}

int find_core(int root) {
	minn=2e9;
	dfs(root,0);
	return new_rt;
}

void dfs2(int u,int fa,int len,int len2) {
	if(len>kk) return ;
	if(is[kk-len]>=1&&is[kk-len]<=2e9) 
		ans=min(is[kk-len]+len2,ans);
	for(int i=0; i<b[u].size(); i++) {
		get(u,v,w,id);
		if(v==fa||vis[id]) continue;
		dfs2(v,u,len+w,len2+1);
	}
}

void add(int u,int fa,int len,int k,int len2) {
	if(len>kk) return ;
	if(k==1) is[len]=min(is[len],len2);
	if(k==-1) is[len]=2e9;
	for(int i=0; i<b[u].size(); i++) {
		get(u,v,w,id);
		if(v==fa||vis[id]) continue;
		add(v,u,len+w,k,len2+1);
	}
}

void calc(int u,int k) { // calc 部分
	for(int i=0; i<b[u].size(); i++) {
		get(u,v,w,id);
		if(vis[id]) continue;
		if(k==1) dfs2(v,u,w,1);
		add(v,u,w,k,1);
	}
}

void solve(int u) {
	get_size(u);
	int t=find_core(u);
	int nxt=0;
	calc(t,1);
	calc(t,-1);
	
	for(int i=0; i<b[t].size(); i++) {
		get(t,v,w,id);
		if(vis[id]) continue;
		
		vis[id]=1;
		solve(v);
		vis[id]=0;
	}
}

int main() {
	read();
	memset(is,0x3f,sizeof(is));
	is[0]=0;
	solve(1);
	if(ans==2e9) puts("-1");
	else cout<<ans<<endl;
    return 0;
}

2022/8/16 14:14
加载中...