题解 | #Max Flow#

咦，竟然之前做过

题解：是一道很经典的树差分模板题，

点差分我们需要让cnt[s]++,让cnt[t]++，而让他们的cnt[lca]--，cnt[faher(lca)]--;
边差分cnt[s]++ ， cnt[t]++ ，cnt[LCA]-=2

边差分：边差分的话要把边的权值存在他连着的儿子节点上，然后儿子节点的权值就是这条边的边权了，
u至v路径上所有边的边权+1，那么c[u]++,c[v]++,c[lca]-=2,可以在多次更新树链之后，得到某边权值。

首先我们可以的看到这个题目是在操作了好多边以后最后询问一个答案，这不就是经典树上边差分模板题目吗。
树剖LCA+树差分

代码：

/*Keep on going Never give up*/
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;
const int maxn=1e6+10;
int mod=998244353;

struct node{
    int to,next;
}edge[maxn];

int tot,head[maxn];

void init(){
    memset(head,-1,sizeof head);
}

void adde(int u,int v){
    edge[tot].to=v,edge[tot].next=head[u];
    head[u]=tot++;
    edge[tot].to=u,edge[tot].next=head[v];
    head[v]=tot++;
}
int v[maxn];
int fa[maxn],dep[maxn],siz[maxn],son[maxn];

void dfs1(int u,int f){
    fa[u]=f;
    dep[u]=dep[f]+1;
    siz[u]=1;
    int maxsize=-1;
    for(int i=head[u];~i;i=edge[i].next){
        int v=edge[i].to;
        if(v==f) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>maxsize){
            maxsize=siz[v];
            son[u]=v;
        }
    }
}
int cnt,dfn[maxn],top[maxn],w[maxn];


void dfs2(int u,int t){
    dfn[u]=++cnt;
    top[u]=t;
    w[cnt]=v[u];
    if(!son[u]) return;
    dfs2(son[u],t);
    for(int i=head[u];~i;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}

int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
int b[maxn];

void sol(int x,int fa){
    for(int i=head[x];~i;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa) continue;
        sol(v,x);
        b[x]+=b[v];
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        adde(u,v);
    }
    dfs1(1,1);
    dfs2(1,1);

    for(int i=0;i<k;i++){
        int x,y;
        cin>>x>>y;
        int lca=LCA(x,y);
        b[x]++,b[y]++;
        b[lca]--,b[fa[lca]]--;
    }
    int imax=0;
    sol(1,0);
    for(int i=1;i<=n;i++){
        imax=max(imax,b[i]);
    }
    cout<<imax<<endl;


}