求助样例无法通过
查看原帖
求助样例无法通过
361141
_JF_殉情楼主2022/12/11 06:16
#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10;
vector<int> g[N<<1];
int d[N],dep[N],fa[N][2];
int n,T;
int maxx=-INT_MAX;
inline int read(){
  	int x=0,w=1;char ch=0;
  	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
  	while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
  	return x*w;
}

inline void write(int x){
  	static int sta[35];int top=0;
  	do{sta[top++]=x%10,x/=10;}while (x);
  	while(top)putchar(sta[--top]+48);
}
void dfs(int u,int fath)
{
	fa[u][0]=fath;
	dep[u]=dep[fath]+1;
	for(int i=1;(1<<i)<=dep[u];i++)
		fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(v==fath)
			continue;
		dfs(v,u);
	}
}
int lca(int x,int y)
{
    if(dep[x]<dep[y])
        swap(x,y);
    int q=dep[x]-dep[y];
    for(int i=0;i<=20;i++)
        if((1<<i)&q)
            x=fa[x][i];
    if(x==y)
        return x;
    for(int i=20;i>=0;i--)
    {
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    }
    return fa[x][0];
}
void dfs2(int u,int fath)
{
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(v==fath)
			continue;
		dfs2(v,u);
		d[u]+=d[v];
	}
	maxx=max(maxx,d[u]);
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>T;
	for(int i=1,u,v;i<n;i++)
		cin>>u>>v,g[u].push_back(v),g[v].push_back(u);
	dfs(1,0);
	while(T--)
	{
		int s,t;
		cin>>s>>t;
		d[s]++,d[t]++,d[lca(s,t)]--,d[fa[lca(s,t)][0]]--;
	}
	dfs2(1,0);
	cout<<maxx<<endl;
	return 0;
}

2022/12/11 06:16
加载中...