题目内容
最小割板子
小 E 有一棵有\(n\) 个点的无根树，它的节点编号为\(1\) 到\(n\) ，其中第\(i(i\in [1,n-1])\) 条边连接节点\(u_i\)和\(v_i\) 。同时他还有\(m\)条树上的路径，第\(i\)条路径为从节点\(a_i\)到\(b_i\)的路径 （请注意，可能存在\(a_i=b_i\) 的情况，此时路径退化为一个点）。
但是小 T 并不喜欢这些路径，所以他想对这棵树进行一些破坏从而破坏路径。具体来说，小 T 可以做以下操作任意多次：
选择一个仍然存在的节点，并同时删除这个节点以及与之相连的边（即边的其中一个节点为删除的节点）。
小 T 认为，在经过一系列的破坏后，一条初始的连接节点\(a_i\) 和\(b_i\) 的路径被成功破坏当且仅当以下条件成立：
节点\(a_i\) 和\(b_i\) 中至少一个点已经被删除；或者节点\(a_i\) 和\(b_i\) 都存在，但此时已经不连通。
但是小 T 做破坏需要花费时间，而他还忙着去打乒乓球，所以他想知道他最少做多少次破坏操作才能使得\(m\) 条路径都被破坏。同时，他不希望你只给个答案，所以小 T 要求你构造方案。
\(3\le n\le 2\times 10^5,2\le m\le 2\times 10^5\)
解题思路
前置知识：DFS序、线段树、ST表、LCA。
我们可以很轻松地想到将删去的点点权设为1，而如果某个\(a_i\)到\(b_i\)的路径上点权和大于1，就跳过这一对。
显然，这可以用DFS序，而因为当年上DFS序的时候，是一个阳光明媚的下午，令人昏昏欲睡，而旁边同学精彩的游戏技术又令人忍不住想看看，于是全班都没听课。
所以，我是今天新自学的DFS序。
显然，这是DFS序中的“点改链查”，我们可以用树状数组来实现。
这里顺便说一句，DFS序搭配ST表可以实现LCA，请自行查询资料。
但是每一次我们删除那个点呢？我们可以删除经过最多的点（吗？）。实际上，这是很容易被Hack的，我们可以把\(a_i,b_i\)一起按照\(deep[LCA(a_i,b_i)]\)从大到小排序，每次删除\(LCA(a_i,b_i)\)。
那样，就可以愉快的码字了。
代码
#include<bits/stdc++.h>
using namespace std;
#define N 200004
int in[N],out[N],ch[N*2],st[N][20],lg[N],dfn[N],b[N*2],doit[N],death[N],fu[N];
int n,m,i,j,x,y,t,s,t2;
struct it{int q,w;
}a[N];
vector<int> v[N],u[N];
int sr(int x,int y){if(dfn[x]>dfn[y]) return y;return x;
}
int l(int x){return x&(-x);
}
void add(int a,int x){int go=a;while(go<=2*n){b[go]+=x;go+=l(go);}return ;
}
int sum(int a){int go=a,s=0;while(go){s+=b[go];go-=l(go);}return s;
}
void dfs(int x,int fa){in[x]=++t;dfn[x]=++t2;st[dfn[x]][0]=fa;death[x]=death[fa]+1;fu[x]=fa;for(int i=0;i<v[x].size();i++){if(v[x][i]==fa) continue;u[x].push_back(v[x][i]);dfs(v[x][i],x);}out[x]=++t;return ;
}
int lca(int x1,int y1){int x=x1,y=y1;if(x==y) return x;x=dfn[x];y=dfn[y];if(x>y) swap(x,y);t=lg[y-x];return sr(st[y-(1<<t)+1][t],st[x+1][t]);
}
bool cmp(it e,it r){return death[lca(e.w,e.q)]>death[lca(r.w,r.q)];
}
int main()
{cin>>n>>m;for(i=1;i<n;i++){scanf("%d%d",&x,&y);v[x].push_back(y);v[y].push_back(x);}dfs(1,0);for(i=2;i<=n;i++) lg[i]=lg[i/2]+1;for(i=1;i<=lg[n];i++){for(j=1;j<=n+1-(1<<i);j++){st[j][i]=sr(st[j][i-1],st[j+(1<<i-1)][i-1]);}}for(i=1;i<=n;i++) ch[in[i]]=ch[out[i]]=i;/*for(i=1;i<=n;i++) cout<<in[i]<<" ";cout<<"\n";for(i=1;i<=n;i++) cout<<out[i]<<" ";cout<<"\n";*/for(i=1;i<=m;i++){scanf("%d%d",&a[i].q,&a[i].w);}sort(a+1,a+1+m,cmp);
// cout<<"\n";for(i=1;i<=m;i++){x=a[i].q;y=a[i].w;
// cout<<x<<" "<<y<<" "<<lca(x,y)<<" "<<in[lca(x,y)]<<" "<<out[lca(x,y)]<<"\n";if(sum(in[y])+sum(in[x])-sum(in[lca(x,y)])-sum(in[fu[lca(x,y)]])){ continue;}add(in[lca(x,y)],1);add(out[lca(x,y)],-1);doit[++s]=lca(x,y);
// for(j=1;j<=n*2;j++)cout<<sum(j)-sum(j-1)<<" ";
// cout<<"\n\n";}printf("%d\n",s);sort(doit+1,doit+1+s);for(i=1;i<=s;i++) printf("%d ",doit[i]);
}
/*
10
7
1 2
2 3
3 4
1 5
1 6
5 7
4 8
6 9
3 10
2 9
7 8
5 7
1 9
7 8
7 9
3 6
if(dfn[x]>dfn[y]) swap(x,y);
if(sum(dfn[y]-dfn[x-1])){
continue;
}
add(lca(x,y),1);
doit[++s]=lca(x,y);
*/