题意：对于每一条边，去掉一条边后，生成两颗树，问这两颗树的交集大小。

分析：1、O(n^2)算法：每次都用O(n)的时间去合并两个区间，因此可以从合并这个地方去优化。

        2、可以这么考虑，在遍历树的时候计算去掉的两树的交集，那么每次我们只要把当前点的所有子树合并便可得到当前点的父边的解。

        3、具体实现细节代码见。

复杂度是O(nlog^2n)，具体可以参考大白p234那一道题。

吐槽：手挫，思路一早就有了，就代码一直写得….

/************************************************Author        :DarkTongCreated Time  :2016/9/5 21:20:03File Name     :Hulan_I.cpp*************************************************/#include 
      
       using namespace std;typedef unsigned long long ULL;typedef long long LL;const int INF = 0x3f3f3f3f;const double eps = 1e-9;const int maxn = 200000 + 100;#define MIN 0x80000000#define MAX 0x7fffffffint vis[maxn];struct Splay_Tree{    int ch[maxn][2], r[maxn], val[maxn], s[maxn], cnt[maxn];    queue
       
         ssz;    void init(){        while(!ssz.empty()) ssz.pop();        for(int i=1;i
        
          r[o]) rotate(o, d^1);            }            else            {                cnt[o]+=cn;                if(cnt[o]==vis[x]) --ans;            }        }        maintain(o);    }    void mergeto(int &src, int &dest, int &ans)    {        if(ch[src][0]) mergeto(ch[src][0], dest, ans);        if(ch[src][1]) mergeto(ch[src][1], dest, ans);        ssz.push(src);        insert(dest, val[src], cnt[src], ans);        src = 0;    }}slt;vector
         
           G[maxn];int ans[maxn], val[maxn], n, ha[maxn];map
          
           
            , int> id;int dfs(int u, int fa){ int tmp, sam = 0; slt.insert(ha[u], val[u], 1, sam); for(int i=0;i
            
              slt.s[ha[u]]) { swap(ha[u], ha[v]); sam = tsam; } if(ha[v]) slt.mergeto(ha[v], ha[u], sam); } ans[id[make_pair(min(u, fa), max(u, fa))]] = sam; return sam;}int main(){ int T, cas=1; while(scanf("%d", &n)==1) { memset(vis, 0, sizeof(vis)); memset(ans, 0, sizeof(ans)); memset(ha, 0, sizeof(ha)); slt.init(); for(int i=1;i
             
              v) swap(u, v); id[make_pair(u, v)] = i; G[u].push_back(v); G[v].push_back(u); } id[make_pair(0, 1)] = 0; dfs(1, 0); for(int i=1;i