48pts求条%%%
查看原帖
48pts求条%%%
927580
zhangxiandong091228楼主2024/12/16 20:32

rt

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e4+10;
int n,k,cnt,x,y,ans,f[maxn][21],d[maxn],hd[maxn],sum[maxn];
struct node
{
    int to,next,dis;
}edge[maxn/2];
void add(int from,int to)
{
    edge[++cnt].next=hd[from];
    edge[cnt].to=to;
    hd[from]=cnt;
}
int max(int a,int b){return a>b?a:b;}
void dfs(int u,int fa)
{
    f[u][0]=fa;
    d[u]=d[fa]+1;
    for(int i=1;(1<<i)<=d[u];i++)
		f[u][i]=f[f[u][i-1]][i-1];
    for(int i=hd[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v!=fa) dfs(v,u);
    }
}
int lca(int u,int v)
{
    if(d[u]<d[v])
		swap(u,v);
    for(int i=20;i>=0;i--)
    {
        if((1<<i)<=d[u]-d[v])
            u=f[u][i];
    }
    if(u==v) return u;
    for(int i=20;i>=0;i--)
    {
        if(f[u][i]!=f[v][i])
        {
            u=f[u][i];
            v=f[v][i];
        }
    }
    return f[u][0];
}
void dsf(int u,int fa)
{
    for(int i=hd[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v!=fa)
        {
            dsf(v,u);
            sum[u]+=sum[v];
        }
    }
    ans=max(ans,sum[u]);
}
int main()
{
   	cin>>n>>k;
    for(int i=1,u,v;i<=n-1;++i)
    {
		cin>>u>>v;
        add(u,v);
		add(v,u);
    }
    dfs(1,0);
    while(k--)
    {
		cin>>x>>y;
        int op=lca(x,y);
        sum[x]++;
		sum[y]++;
        sum[op]--;
		sum[f[op][0]]--;
    }
    dsf(1,0);
    cout<<ans<<endl;
}

RE2-7,14,15 求大佬指点%%%

2024/12/16 20:32
加载中...