1 条题解

  • 1
    @ 2022-04-23 19:07:55
    #include <bits/stdc++.h>
    using namespace std;
    #define maxn 50010
    #define ll long long
    #define res register int
    struct Node {
        int to,next;
    };
    Node edge[maxn<<2]; //链式前向星要多开几倍数组
    int head[maxn<<2],power[maxn],n,m,d[maxn],fa[maxn][30],ans,num;
    
    inline int read() { //快读
        int s=0;
        char c=getchar();
        while (c<'0' || c>'9') c=getchar();
        while (c>='0' && c<='9') s=s*10+c-'0',c=getchar();
        return s;
    }
    //链式前向星
    inline void add(int x,int y) {
        edge[++num].to=y,edge[num].next=head[x],head[x]=num;
    }
    //接下来是初始化
    inline void work(int u,int fath) {
        d[u]=d[fath]+1,fa[u][0]=fath;
        for (res i=0; fa[u][i]; ++i)
            fa[u][i+1]=fa[fa[u][i]][i];
        for (res i=head[u]; i; i=edge[i].next) {
            int e=edge[i].to;
            if (e!=fath) work(e,u);
        }
    }
    //倍增求LCA
    inline int Lca(int u,int v) {
        if (d[u]>d[v]) swap(u,v);
        for (res i=20; i>=0; --i) if (d[u]<=d[v]-(1<<i)) v=fa[v][i];
        if (u==v) return u;
        for (res i=20; i>=0; --i) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
        return fa[u][0];
    }
    //累计
    inline void Get(int u,int fath) {
        for (res i=head[u]; i; i=edge[i].next) {
            int e=edge[i].to;
            if (e==fath) continue;
            Get(e,u);
            power[u]+=power[e];
        }
        ans=max(ans,power[u]);
    }
    
    int main() {
        n=read(),m=read();
        int x,y;
        for (res i=1; i<n; ++i) {
            x=read(),y=read();
            add(x,y);
            add(y,x);
        }
        work(1,0);
        for (res i=1; i<=m; ++i) {
            x=read(),y=read();
            int lca=Lca(x,y);
            ++power[x];
            ++power[y];
            --power[lca];
            --power[fa[lca][0]]; //树上差分
        }
        Get(1,0);
        printf("%d\n",ans);
        return 0;
    }
    
    
  • 1

信息

ID
1131
难度
8
分类
线段树最近公共祖先差分 点击显示
标签
递交数
1
已通过
1
通过率
100%
上传者