题目：http://acm.hdu.edu.cn/showproblem.php?pid=5511
题意：割一些边使得无向图变成不连通的，并且恰好割了两条给定生成树上的边。满足非树边两段一定在给定生成树的根的不同子树里。求最小边数。
看了题解。
一直考虑割出来的是树上的连通块之类的。
其实考虑讨论那两条树边的关系。
1.两条边是祖先--后代关系。
答案就是它们之间夹着的连通块伸出去的非树边条数+2。所以两条边离得越近越好。
那么就是一个点的父亲边+该点父亲的父亲边。O(n)枚举即可。
注意1号点没有父亲边。
2.两条边不是祖先--后代关系。
那么两条边引导了两个子树。答案就是这两个子树伸出去的非树边条数 - 两个子树相互的非树边条数*2 + 2 。
然后又不太会了。
其实考虑答案形如 d[ x ] + d[ y ] - 2*cnt( x, y ) ，那么枚举 x ，用线段树维护 d[ y ] - 2*cnt( x, y ) 的最小值即可。注意1号点不能参与。
那么就是线段树合并得到 cnt( ) ，再加入当前根 cr 的贡献，就是 cr 连出去的点 y ， y 到父亲的链上的值都 - 2 。
还要把 cr 的位置设成 INF 。
动态开点。每个点的初值是 “只考虑 d[ ] 不考虑 cnt ，区间最小值” 。这个可以预处理。借鉴了 Claris 的写法，把该值记在以 cr << 1 , cr<<1|1 为结构得到的线段树角标上。
注意如果没有左孩子或右孩子之类的，调用的是上述初值而不是 0 或 INF 。
直接线段树合并，空间不行。考虑像 dsu on tree 一样，每个点继承其重孩子的线段树。线段树合并之后，轻孩子的线段树节点都删掉。这样同时又 log 个线段树，空间可行。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define pb push_back
#define ls Ls[cr]
#define rs Rs[cr]
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
int Mx(int a,int b){return a>b?a:b;}
int Mn(int a,int b){return a<b?a:b;}
const int N=2e4+,M=N*,INF=1e6+;
int n,m,hd[N],xnt,to[N<<],nxt[N<<],rd[N],ans;
int tim,dfn[N],dy[N],top[N],son[N],siz[N],fa[N],dep[N];
int rt[N],tot,Ls[M],Rs[M],mn[M],tg[M];
int w[N<<],dlpl[M],dtop;
vector<int> vt[N];
void init()
{
xnt=; for(int i=;i<=n;i++)hd[i]=;
tim=tot=dtop=;
for(int i=;i<=n;i++)vector<int>().swap(vt[i]);
for(int i=;i<=n;i++)son[i]=;///
for(int i=;i<=n;i++)rt[i]=;///
for(int i=;i<=n*;i++)w[i]=INF;
}
void add(int x,int y)
{to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}
void ini_build(int l,int r,int cr)
{
if(l==r)
{if(dy[l]==)w[cr]=INF;else w[cr]=rd[dy[l]];return;}
int mid=l+r>>;
ini_build(l,mid,cr<<);
ini_build(mid+,r,cr<<|);
w[cr]=Mn(w[cr<<],w[cr<<|]);
}
void dfs(int cr,int f)
{
fa[cr]=f; dep[cr]=dep[f]+; siz[cr]=;
rd[cr]=vt[cr].size();
for(int i=hd[cr],v;i;i=nxt[i])
if((v=to[i])!=f)
{
dfs(v,cr); rd[cr]+=rd[v]; siz[cr]+=siz[v];
if(siz[v]>siz[son[cr]])son[cr]=v;
}
if(cr==)return;//
for(int i=hd[cr],v;i;i=nxt[i])
if((v=to[i])!=f)
ans=Mn(ans,rd[cr]-rd[v]);
}
void dfsx(int cr,int f)
{
dfn[cr]=++tim; dy[tim]=cr;
if(son[cr]){ top[son[cr]]=top[cr];dfsx(son[cr],cr);}
for(int i=hd[cr],v;i;i=nxt[i])
if((v=to[i])!=f&&v!=son[cr])
{ top[v]=v; dfsx(v,cr);}
}
int nwnd(int id)
{
int cr;
if(dtop)cr=dlpl[dtop--]; else cr=++tot;
ls=rs=tg[cr]=; mn[cr]=w[id]; return cr;
}
void del(int x){ dlpl[++dtop]=x;}
void pshp(int cr,int id)//if!!!
{
if(ls)mn[cr]=mn[ls]; else mn[cr]=w[id<<];
if(rs)mn[cr]=Mn(mn[cr],mn[rs]);
else mn[cr]=Mn(mn[cr],w[id<<|]);
}
void pshd(int cr,int id)
{
if(!tg[cr])return; int w=tg[cr]; tg[cr]=;
if(!ls)ls=nwnd(id<<); if(!rs)rs=nwnd(id<<|);
tg[ls]+=w; tg[rs]+=w; mn[ls]+=w; mn[rs]+=w;
}
void mdfy(int l,int r,int &cr,int id,int p)
{
if(!cr)cr=nwnd(id); if(l==r){mn[cr]=INF;return;}
int mid=l+r>>; pshd(cr,id);
if(p<=mid)mdfy(l,mid,ls,id<<,p);
else mdfy(mid+,r,rs,id<<|,p);
pshp(cr,id);
}
void add(int l,int r,int &cr,int id,int L,int R)
{
if(!cr)cr=nwnd(id);
if(l>=L&&r<=R){tg[cr]-=;mn[cr]-=;return;}
int mid=l+r>>; pshd(cr,id);
if(L<=mid)add(l,mid,ls,id<<,L,R);
if(mid<R)add(mid+,r,rs,id<<|,L,R);
pshp(cr,id);
}
void mrg(int l,int r,int &cr,int id,int v)
{
if(!cr){cr=v;return;} if(!v)return;
if(l==r)
{
if(mn[cr]==INF||mn[v]==INF)mn[cr]=INF;
else {mn[cr]+=mn[v]; mn[cr]-=rd[dy[l]];}
del(v); return;
}
int mid=l+r>>; pshd(cr,id); pshd(v,id);
mrg(l,mid,ls,id<<,Ls[v]);
mrg(mid+,r,rs,id<<|,Rs[v]);
pshp(cr,id); del(v);
}
void solve(int cr)
{
if(son[cr]){ solve(son[cr]); rt[cr]=rt[son[cr]];}
for(int i=hd[cr],v;i;i=nxt[i])
if((v=to[i])!=fa[cr]&&v!=son[cr])
{
solve(v); mrg(,n,rt[cr],,rt[v]);
}
if(cr==)return;////!!!
mdfy(,n,rt[cr],,dfn[cr]);
for(int i=,lm=vt[cr].size();i<lm;i++)
{
int x=vt[cr][i];
while(top[x]!=)
{
add(,n,rt[cr],,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(x>)add(,n,rt[cr],,,dfn[x]);///no 1
}
ans=Mn(ans,rd[cr]+mn[rt[cr]]);
}
int main()
{
int T=rdn();
for(int t=;t<=T;t++)
{
n=rdn();m=rdn(); init();
for(int i=,u,v;i<n;i++)
{
u=rdn();v=rdn();add(u,v);add(v,u);
}
for(int i=n,u,v;i<=m;i++)
{
u=rdn();v=rdn();
vt[u].pb(v); vt[v].pb(u);
}
ans=INF; dfs(,);
top[]=; dfsx(,);
ini_build(,n,); solve();
printf("Case #%d: %d\n",t,ans+);
}
return ;
}