pro：给定N+1个点的树，有M对关键点，现在让你破坏最少的点，使得M对关键点不连通。
sol：贪心，我们把M对点按照LCA深度排序，每次破坏LCA。 如果一对点(u,v,lca)，u-lca-v有点被破坏，则可以不用破坏新的点。 我们可以用dfs序+树状数组来处理。 如果破坏了一个点，则给它的子树都+1。 那么u-lca-v有点被破坏等价于，u或者v至少一个属于已经被破坏的点的子树，树状数组查询即可。
#include<bits/stdc++.h> #define ll long long #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=200010; int fa[maxn][15],Laxt[maxn],Next[maxn],To[maxn],dep[maxn]; int sum[maxn],cnt,in[maxn],times,out[maxn],ans; struct fcy{ int u,v,lca; }s[maxn]; bool cmp(fcy x,fcy y){ return dep[x.lca]>dep[y.lca];} void add(int x,int val){ while(x<=times){ sum[x]+=val; x+=(-x)&x;}} int query(int x){int res=0; while(x){ res+=sum[x];x-=(-x)&x;}return res;} void adde(int u,int v){ Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v;} void dfs(int u,int f) { in[u]=++times; dep[u]=dep[f]+1; fa[u][0]=f; for(int i=Laxt[u];i;i=Next[i]){ if(To[i]!=f) dfs(To[i],u); } out[u]=times; } int LCA(int u,int v) { if(dep[u]<dep[v]) swap(u,v); for(int i=14;i>=0;i--) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i]; if(u==v) return u; for(int i=14;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0]; } int main() { int N,Q,u,v; while(~ scanf("%d",&N)){ N++; ans=0; rep(i,1,N) Laxt[i]=0; cnt=0; rep(i,1,N-1){ scanf("%d%d",&u,&v); u++; v++; adde(u,v); adde(v,u); } rep(i,1,times) sum[i]=0; times=0; dfs(1,0); rep(i,1,14) rep(j,1,N) fa[j][i]=fa[fa[j][i-1]][i-1]; scanf("%d",&Q); rep(i,1,Q){ scanf("%d%d",&s[i].u,&s[i].v); s[i].u++; s[i].v++; s[i].lca=LCA(s[i].u,s[i].v); } sort(s+1,s+Q+1,cmp); rep(i,1,Q){ int t=query(in[s[i].u])+query(in[s[i].v]); if(!t) { ans++; add(in[s[i].lca],1); add(out[s[i].lca]+1,-1); } } printf("%d ",ans); } return 0; }