题目：https://www.luogu.org/problemnew/show/P3128
树上差分。用离线lca，邻接表存好方便。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=5e4+5,M=1e5+5; int n,m,hd[N],xnt,fa[N],pre[N],c[N],qhd[N],t[M<<1],nxt[M<<1],ans; bool vis[N]; struct Ed{ int nxt,to;Ed(int n=0,int t=0):nxt(n),to(t) {} }ed[N<<1]; int rdn() { int ret=0;char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch>='0'&&ch<='9')(ret*=10)+=ch-'0',ch=getchar(); return ret; } void add(int x,int y) { ed[++xnt]=Ed(hd[x],y);hd[x]=xnt; ed[++xnt]=Ed(hd[y],x);hd[y]=xnt; } void ad(int x,int y) { t[++xnt]=y;nxt[xnt]=qhd[x];qhd[x]=xnt; t[++xnt]=x;nxt[xnt]=qhd[y];qhd[y]=xnt; } int find(int a){return fa[a]==a?a:fa[a]=find(fa[a]);} void dfs(int cr) { vis[cr]=1; for(int i=qhd[cr],v;i;i=nxt[i]) if(vis[v=t[i]]) { int lca=find(v),pr=pre[lca]; c[cr]++;c[v]++;c[lca]--;c[pr]--; } for(int i=hd[cr],v;i;i=ed[i].nxt) if((v=ed[i].to)!=pre[cr]) { pre[v]=cr;dfs(v); } fa[cr]=pre[cr]; } void dfsx(int cr) { for(int i=hd[cr],v;i;i=ed[i].nxt) if((v=ed[i].to)!=pre[cr]) dfsx(v),c[cr]+=c[v]; ans=max(ans,c[cr]); } int main() { n=rdn();m=rdn();int x,y; for(int i=1;i<n;i++) { x=rdn();y=rdn();add(x,y); } xnt=0; for(int i=1;i<=m;i++) { x=rdn();y=rdn();ad(x,y); } for(int i=1;i<=n;i++)fa[i]=i; dfs(1);dfsx(1); printf("%d ",ans); return 0; }