求助13pts、
查看原帖
求助13pts、
752094
MornHus楼主2023/1/22 18:13

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0'){
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    return x;
}
int ans;
int tt;
int n,k,u,v;
vector<int>tree[50001];
int diff[50001];
int dep[50001];
int f[50001][17];
void dfs(int now,int fa){
    dep[now]=dep[fa]+1;f[now][0]=fa;
    for(int i=0;f[now][i];i++){
        f[now][i+1]=f[f[now][i]][i];
    }
    for(int i=0;i<tree[now].size();i++){
        if(tree[now][i]!=fa)dfs(tree[now][i],now);
    }
}
int lca(int a,int b){
    int temp;
    if(dep[a]<dep[b])swap(a,b);
    temp=dep[a]-dep[b];
    for(int i=0;(1<<i)<=temp;i++){
        if((1<<i)&temp){
            a=f[a][i];
        }
    }
    if(a==b)return a;
    for(int i=tt;i>=0;i--){
        if(f[a][i]!=f[b][i]){
            a=f[a][i];
            b=f[a][i];
        }
    }
    return f[a][0];
}
void getans(int now,int fa){
    for(int i=0;i<tree[now].size();i++){
        if(tree[now][i]==fa)continue;
        getans(tree[now][i],now);
        diff[now]+=diff[tree[now][i]];
    }
    ans=max(ans,diff[now]);
}
int main(){
    n=read();
    k=read();
    tt=(int)(log(n)/log(2));
    for(int i=1;i<n;i++){
        u=read();
        v=read();
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    dfs(1,0);
    int LCA;
    for(int i=1;i<=k;i++){
        u=read();v=read();
        LCA=lca(u,v);
        diff[u]++;diff[v]++;diff[LCA]--;diff[f[LCA][0]]--;
    }
    getans(1,0);
    cout<<ans;
    return 0;
} 
2023/1/22 18:13
加载中...