BJOI2014 大融合

Description

小强要在N个孤立的星球上建立起一套通信系统。这套通信系统就是连接N个点的一个树。这个树的边是一条一条添加上去的。在某个时刻，一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量。

例如，在上图中，现在一共有了5条边。其中，(3,8)这条边的负载是6，因为有六条简单路径2-3-8,2-3-8-7,3-8,3-8-7,4-3-8,4-3-8-7路过了(3,8)。

现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的询问。

Input

第一行包含两个整数N,Q，表示星球的数量和操作的数量。星球从1开始编号。

接下来的Q行，每行是如下两种格式之一：

A x y 表示在x和y之间连一条边。保证之前x和y是不联通的。

Q x y 表示询问(x,y)这条边上的负载。保证x和y之间有一条边。

Output

对每个查询操作，输出被查询的边的负载。

Sample Input

8 6

A 2 3

A 3 4

A 3 8

A 8 7

A 6 5

Q 3 8

Sample Output

Data Constraint

对于40%的数据，N,Q≤1000

对于100%的数据，1≤N,Q≤100000

先把所有边连起来，然后排dfs序来判断每次连的点中哪个作为父亲，哪个作为儿子。然后进行操作，用并查集来维护各个连通块，用链剖维护size，每个更新这个连通块内所有父亲的值，用倍增找这个连通块内离它最远的父亲。

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;

struct tree{
    int x,z,q,bz;
}tr[500011];

bool vis[100011];
int top[100011],son[100011],dfn[100011],num[100011],size[100011];
int g[100011],y[200022],next[200022],f[100011],fa[100011],kind[100011],nn[100011];
int edge[100011][3],fat[100011][18];
char s[11];
ll ap,ple,xzq;
int i,j,n,q,x,z,t,tt,tot,e;

void swap(int &a,int &b)
{
    int t;
    t=a;
    a=b;
    b=t;
}

int find(int r)
{
    if(f[r]==r)return r;
    else f[r]=find(f[r]);
    return f[r];
}

void star(int i,int j)
{
    tt++;
    next[tt]=g[i];
    g[i]=tt;
    y[tt]=j;
    tt++;
    next[tt]=g[j];
    g[j]=tt;
    y[tt]=i;
}

void build_chain(int root)
{
    int x;
    x=root;
    while(x!=0){
        num[x]=++tot;
        top[x]=root;
        x=son[x];
    }
}

void Dfs(int x,int faf)
{
    int j,k;
    size[x]=1;
    fa[x]=faf;
    fat[x][0]=faf;
    vis[x]=true;
    dfn[x]=++t;
    j=g[x];
    while(j!=0){
        k=y[j];
        if(!vis[k]){
            Dfs(k,x);
            size[x]+=size[k];
            if(size[k]>size[son[x]]){
                if(son[x])build_chain(son[x]);
                son[x]=k;
            }
            else build_chain(k);
        }
        j=next[j];
    }
}

void down(int t)
{
    if(tr[t].x==tr[t].z)return;
    if(tr[t].bz){
        tr[t+t].bz+=tr[t].bz;
        tr[t+t].q+=tr[t].bz;
        tr[t+t+1].bz+=tr[t].bz;
        tr[t+t+1].q+=tr[t].bz;
        tr[t].bz=0;
    }
}

void build(int l,int r,int t)
{
    int mid;
    if(l==r){
        tr[t].x=l;
        tr[t].z=r;
        tr[t].q=1;
        tr[t].bz=0;
        nn[l]=t;
        return;
    }
    mid=(l+r)/2;
    tr[t].x=l;
    tr[t].z=r;
    build(l,mid,t+t);
    build(mid+1,r,t+t+1);
}

void insert(int t,int l,int r,int x)
{
    int mid;
    down(t);
    if(tr[t].x==l&&tr[t].z==r){
        tr[t].q+=x;
        tr[t].bz+=x;
        return;
    }
    mid=(tr[t].x+tr[t].z)/2;
    if(r<=mid)insert(t+t,l,r,x);
    if(l>mid)insert(t+t+1,l,r,x);
    if(l<=mid&&r>mid){
        insert(t+t,l,mid,x);
        insert(t+t+1,mid+1,r,x);
    }
}

int ask(int t,int x)
{
    int mid;
    down(t);
    if(tr[t].x==tr[t].z)return tr[t].q;
    mid=(tr[t].x+tr[t].z)/2;
    if(x<=mid)return ask(t+t,x);
    else return ask(t+t+1,x);
}

int Finn(int x,int z)
{
    int i,q;
    q=z;
    for(i=17;i>=0;i--){
        f[fat[q][i]]=find(f[fat[q][i]]);
        if(f[fat[q][i]]==x)q=fat[q][i];
    }
    return q;
}

void change(int x,int z,int q)
{
    int t;
    while(x!=0){
        if(top[q]==top[x]){
            insert(1,num[q],num[x],z);
            return;
        }
        else{
            insert(1,num[top[x]],num[x],z);
            x=fa[top[x]];
        }
    }
}

int main()
{
    scanf("%d%d",&n,&q);
    for(i=1;i<=q;i++){
        scanf("%s",&s);
        scanf("%d%d",&x,&z);
        edge[i][1]=x;
        edge[i][2]=z;
        if(s[0]=='A')star(x,z);
        if(s[0]=='A')kind[i]=1;
        else kind[i]=2;
    }
    memset(vis,false,sizeof(vis));
    for(i=1;i<=n;i++){
        if(!vis[i]){
            Dfs(i,0);
            build_chain(i);
        }
    }
    for(i=1;i<=17;i++){
        for(j=1;j<=n;j++){
            fat[j][i]=fat[fat[j][i-1]][i-1];
        }
    }
    build(1,n,1);
    for(i=1;i<=n;i++)f[i]=i;
    for(i=1;i<=q;i++){
        if(kind[i]==1){
            if(dfn[edge[i][1]]>dfn[edge[i][2]])swap(edge[i][1],edge[i][2]);
            x=find(f[edge[i][1]]);
            z=find(f[edge[i][2]]);
            if(x!=z)f[z]=x;
            e=Finn(x,edge[i][2]);
            ple=ask(1,num[edge[i][2]]);
            change(edge[i][1],ple,e);
        }
        else{
            if(dfn[edge[i][1]]>dfn[edge[i][2]])swap(edge[i][1],edge[i][2]);
            f[edge[i][1]]=find(f[edge[i][1]]);
            ap=ask(1,num[f[edge[i][1]]]);
            ple=ask(1,num[edge[i][2]]);
            xzq=(ap-ple)*ple;
            printf("%lld
",xzq);
        }
    }
}