BZOJ-1036: [ZJOI2008]树的统计Count（轻重树链剖分 LCT）

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1036

时间：

LCT(O((n+m) log n))：

9922720e0cf3d7cad689985bf01fbe096b63a9a4.jpg.png

树链剖分(O((n+m) log^2 n))：

b21bb051f81986184e5848a948ed2e738bd4e684.jpg.png

代码（第一次尝试写轻重树链剖分，O(n log^2 n)的复杂度还可以。。下次再来写块状树，lct的代码链接（https://www.jianshu.com/p/6090162a7759 度娘一次不给贴太长的染色代码，只能代码另发一次了。。。）函数式线段树MLE了,空间O((n log n + q) log n)各种巨大啊 TAT）：

（树链的太长贴不了染色的。。。）

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

using namespace std;

#define MAXN 30001

#define inf 0x7fffffff

#define MAXM 200001

#define clear(x) memset(x,0,sizeof(x))

struct edge{

    int t;

    edge *next;

    edge (){

        next=NULL;

    }

}*he[MAXN];

int n,m,par[MAXN],Si[MAXN],Ch[MAXN],Que[MAXM][3],Index=0,Num=0,Id[MAXN],Arr[MAXN],Pos[MAXN],Fir[MAXN],Lca[MAXM],fat[MAXN],w[MAXN];

bool f[MAXN];

void AddEdge(int s,int t){edge *p=new(edge);p->t=t;p->next=he[s];he[s]=p;}

void Dfs_Si(int v){

    f[v]=false;

    Si[v]=1;

    int maxSi=0;

    for(edge *p=he[v];p;p=p->next){

        if(f[p->t]){

            par[p->t]=v;

            Dfs_Si(p->t);

            Si[v]+=Si[p->t];

            if(Si[p->t]>maxSi){

                maxSi=Si[p->t];

                Ch[v]=p->t;

            }

        }

    }

}

void Heavy_Edge(int v,bool flag){

    if(flag) Fir[++Index]=v;

    Id[v]=Index;

    Arr[Pos[v]=++Num]=v;

    f[v]=false;

    if(Ch[v])Heavy_Edge(Ch[v],false);

    for(edge *p=he[v];p;p=p->next){

        if(f[p->t]&&p->t!=Ch[v]){

            Heavy_Edge(p->t,true);

        }

    }

}

struct lca_type {

    int t,r;

    lca_type *next;

}*Fro[MAXN];

void Insert(int s,int t,int r){

    lca_type *p=new(lca_type);

    p->t=t;p->r=r;p->next=Fro[s];Fro[s]=p;

}

int Find(int v){

    int i,j=v;

    for(i=v;fat[i];i=fat[i]);

    while(fat[j]){

        int k=fat[j];

        fat[j]=i;

        j=k;

    }

    return i;

}

void Tarjan(int v){

    f[v]=false;

    for(lca_type *p=Fro[v];p;p=p->next)if(!f[p->t])  Lca[p->r]=Find(p->t);

    for(edge *p=he[v];p;p=p->next)

        if(f[p->t]){Tarjan(p->t);fat[Find(p->t)]=v;}

}

struct node{

    int l,r,Max,Sum;

} T[MAXN*3];

void Build_SegT(int l,int r,int t){

    T[t].l=l,T[t].r=r;

    if(l==r){

        T[t].Max=T[t].Sum=w[Arr[l]];

        return;

    }

    Build_SegT(l,(l+r)>>1,t<<1);

    Build_SegT(((l+r)>>1)+1,r,(t<<1)^1);

    T[t].Max=max(T[t<<1].Max,T[(t<<1)^1].Max);

    T[t].Sum=T[t<<1].Sum+T[(t<<1)^1].Sum;

}

void INIT(){

    scanf("%d",&n);

    memset(he,0,sizeof(he));

    for(int i=0;i++<n-1;){

        int s,t;

        scanf("%d%d",&s,&t);

        AddEdge(s,t),AddEdge(t,s);

    }

    clear(par),clear(Ch);

    memset(f,true,sizeof(f));

    Dfs_Si(1);

    memset(f,true,sizeof(f));

    Heavy_Edge(1,true);

    for(int i=0;i++<n;)scanf("%d",&w[i]);

    memset(Fro,0,sizeof(Fro));

    scanf("%d",&m);

    for(int i=0;i++<m;){

        char s[20];

        scanf("%s%d%d",&s,&Que[i][1],&Que[i][2]);

        if(s[0]=='C') Que[i][0]=0

        ;else{

            if(s[1]=='M') Que[i][0]=1

            ;  else Que[i][0]=2;

            Insert(Que[i][1],Que[i][2],i);

            Insert(Que[i][2],Que[i][1],i);

        }

    }

    memset(f,true,sizeof(f));clear(fat);

    Tarjan(1);

    Build_SegT(1,n,1);

}

void Change(int v,int u,int t){

    if(T[t].l==T[t].r){

        T[t].Sum=T[t].Max=u;

        return;

    }

    if(v<=((T[t].l+T[t].r)>>1))Change(v,u,t<<1)

    ;  else Change(v,u,(t<<1)^1);

    T[t].Sum=T[t<<1].Sum+T[(t<<1)^1].Sum;

    T[t].Max=max(T[t<<1].Max,T[(t<<1)^1].Max);

}

int Max(int l,int r,int t){

    if(T[t].l==l&&T[t].r==r)return T[t].Max;

    int mid=(T[t].l+T[t].r)>>1;

    if(r<=mid)return Max(l,r,t<<1);

    if(l>mid)return Max(l,r,(t<<1)^1);

    return max(Max(l,mid,t<<1),Max(mid+1,r,(t<<1)^1));

}

int Sum(int l,int r,int t){

    if(T[t].l==l&&T[t].r==r)return T[t].Sum;

    int mid=(T[t].l+T[t].r)>>1;

    if(r<=mid)return Sum(l,r,t<<1);

    if(l>mid)return Sum(l,r,(t<<1)^1);

    return Sum(l,mid,t<<1)+Sum(mid+1,r,(t<<1)^1);

}

int GM(int v,int u){

    int rec=-inf;

    while(1){

        if(Id[v]==Id[u])return max(rec,Max(Pos[u],Pos[v],1))

        ; else{rec=max(rec,Max(Pos[Fir[Id[v]]],Pos[v],1));v=par[Fir[Id[v]]];}

    }

}

int GS(int v,int u){

    int rec=0;

    while(1){

        if(Id[v]==Id[u])return rec+Sum(Pos[u],Pos[v],1);  else rec+=Sum(Pos[Fir[Id[v]]],Pos[v],1),v=par[Fir[Id[v]]];

    }

}

void Solve(){

    for(int i=0;i++<m;){

        if(!Que[i][0]){

            Change(Pos[Que[i][1]],Que[i][2],1);

            w[Que[i][1]]=Que[i][2];

        }else{

            if(Que[i][0]==1)printf("%d\n",max(GM(Que[i][1],Lca[i]),GM(Que[i][2],Lca[i])));  else printf("%d\n",GS(Que[i][1],Lca[i])+GS(Que[i][2],Lca[i])-w[Lca[i]]);

        }

    }

}

int main(){

    INIT();

    Solve();

    return 0;

}

BZOJ-1036: [ZJOI2008]树的统计Count（轻重树链剖分 LCT）

推荐阅读更多精彩内容