题目：

题意：割一些边使得无向图变成不连通的，并且恰好割了两条给定生成树上的边。满足非树边两段一定在给定生成树的根的不同子树里。求最小边数。

看了题解。

　　一直考虑割出来的是树上的连通块之类的。

　　其实考虑讨论那两条树边的关系。

　　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
      
       #include
       
        #include
        
         #include
         
          #define pb push_back#define ls Ls[cr]#define rs Rs[cr]using namespace std;int rdn(){  int ret=0;bool fx=1;char ch=getchar();  while(ch>'9'||ch<'0'){
    if(ch=='-')fx=0;ch=getchar();}  while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',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
          

vt[N];void init(){ xnt=0; for(int i=1;i<=n;i++)hd[i]=0; tim=tot=dtop=0; for(int i=1;i<=n;i++)vector

().swap(vt[i]); for(int i=1;i<=n;i++)son[i]=0;/// for(int i=1;i<=n;i++)rt[i]=0;/// for(int i=1;i<=n*4;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]==1)w[cr]=INF;else w[cr]=rd[dy[l]];return;} int mid=l+r>>1; ini_build(l,mid,cr<<1); ini_build(mid+1,r,cr<<1|1); w[cr]=Mn(w[cr<<1],w[cr<<1|1]);}void dfs(int cr,int f){ fa[cr]=f; dep[cr]=dep[f]+1; siz[cr]=1; 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==1)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]=0; 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<<1]; if(rs)mn[cr]=Mn(mn[cr],mn[rs]); else mn[cr]=Mn(mn[cr],w[id<<1|1]);}void pshd(int cr,int id){ if(!tg[cr])return; int w=tg[cr]; tg[cr]=0; if(!ls)ls=nwnd(id<<1); if(!rs)rs=nwnd(id<<1|1); 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>>1; pshd(cr,id); if(p<=mid)mdfy(l,mid,ls,id<<1,p); else mdfy(mid+1,r,rs,id<<1|1,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]-=2;mn[cr]-=2;return;} int mid=l+r>>1; pshd(cr,id); if(L<=mid)add(l,mid,ls,id<<1,L,R); if(mid

<<1|1,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>>1; pshd(cr,id); pshd(v,id); mrg(l,mid,ls,id<<1,Ls[v]); mrg(mid+1,r,rs,id<<1|1,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(1,n,rt[cr],1,rt[v]); } if(cr==1)return;////!!! mdfy(1,n,rt[cr],1,dfn[cr]); for(int i=0,lm=vt[cr].size();i

1)add(1,n,rt[cr],1,2,dfn[x]);///no 1 } ans=Mn(ans,rd[cr]+mn[rt[cr]]);}int main(){ int T=rdn(); for(int t=1;t<=T;t++) { n=rdn();m=rdn(); init(); for(int i=1,u,v;i