求助,6分其余全RE
查看原帖
求助,6分其余全RE
534690
DuskLight楼主2021/9/3 21:28
#include<iostream>
#include<cmath>
#define ll long long 
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
ll fread(){
	int s=0,x=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') x=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		s=s*10+(ch-'0');
		ch=getchar();
	}
	return x==1?s:-s;
}
struct node {
	ll next;
	ll to;
}edge[1000005];

ll n,m,cnt=0,head[200005],num[200005],deep[200005],f[200005][25],ans=-1;
ll chafen[200005];

void add(ll u,ll v){
	edge[++cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
	return ;
}

void dfs(int now,int fa){
       deep[now]=deep[fa]+1;
       f[now][0]=fa;
       for(int i=1;(1<<i)<=deep[now];i++){
       	f[now][i]=f[f[now][i-1]][i-1];
	   }
       for(int i=head[now];i;i=edge[i].next){
       int next=edge[i].to;
       	if(next==fa)continue;
       	dfs(next,now);
	   }
	}


ll lca(int a,int b){
	if(deep[a]<deep[b]) swap(a,b);
	int h=deep[a]-deep[b];
	int k=log2(h);
	for(int i=k;i>=0;i--){
		if(h&(1<<i)){
			a=f[a][i];
		}
	} 
	if(a==b){
		return a;
	}
	k=log2(deep[a]);
	for(int i=k;i>=0;i++){
		if(f[b][i]!=f[a][i]){
			a=f[a][i];
			b=f[b][i];
		}
	}
	return f[a][0];
}

ll dfs2(ll now,ll father){
	for(int i=head[now];i;i=edge[i].next){    //求和 
		if(edge[i].to==father)continue;
		dfs2(edge[i].to,now);  //递归 
		chafen[now]+=chafen[edge[i].to];  //从最底层不断往上累加 
	}  //差分数组累加就是值! 
	ans=max(ans,chafen[now]);
	return ans;
}

int main(){
	n=fread();
	m=fread();
	for(int i=1;i<n;i++){
		ll u=fread();
		ll v=fread();
		add(u,v);
		add(v,u);
	}
	
	deep[0]=1;
	
	dfs(1,0);

	for(int i=1;i<=m;i++){
		ll u=fread();
		ll v=fread();
		ll temp=lca(u,v);
		chafen[u]++;
		chafen[v]++;
		chafen[temp]--;
		chafen[f[temp][0]]--; 
		}  //树上拆分模板,左右子+1,LCA及LCA的父亲-1 
	dfs2(1,0);
	printf("%lld",ans);
	return 0;
}
2021/9/3 21:28
加载中...