树剖好题……

这能说明几个问题：

1. 人傻自带大常数
2. 不看题解难AC

需要注意的是某些线段树的区间的合并……对应到树上时不要搞错了……

代码（巨长慎看）：

/**************************************************************
    Problem: 2243
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4504 ms
    Memory:16544 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <bitset>
using namespace std;
#define REP(i,n) for(i=0;i<(n);i++)
#define REPB(i,n) for(i=1;i<=(n);i++)
#define SEG_CS int o,int L,int R
#define DEF_MID int M=L+(R-L)/2
#define DEF_CLDS int lc=o*2,rc=o*2+1
const int maxn=100001;
const int maxnode=maxn*4;
   
// Segment Tree
int sumv[maxnode],first[maxnode],last[maxnode],setv[maxnode];
inline void maintain(SEG_CS){
    DEF_CLDS;
    if(R>L){
        first[o]=first[lc];
        last[o]=last[rc];
        sumv[o]=sumv[lc]+sumv[rc];
        if(last[lc]==first[rc])
            sumv[o]--;
    }
    if(setv[o]>=0){
        first[o]=setv[o];
        last[o]=setv[o];
        sumv[o]=1;
    }
}
inline void pushdown(int o){
    DEF_CLDS;
    if(setv[o]>=0){
        setv[lc]=setv[rc]=setv[o];
        setv[o]=-1;
    }
}
int ql,qr,v;
void update1(SEG_CS){
    DEF_CLDS;
    if(ql<=L && R<=qr){
        setv[o]=v;
    }else{
        pushdown(o);
        DEF_MID;
        if(ql<=M)
            update1(lc,L,M);
        else
            maintain(lc,L,M);
        if(qr>M)
            update1(rc,M+1,R);
        else
            maintain(rc,M+1,R);
    }
    maintain(o,L,R);
}
int sum1,cur_first,cur_last;
void query1(SEG_CS){
    DEF_CLDS;
    if(setv[o]>=0){
        if(setv[o]!=cur_last){
            cur_last=setv[o];
            sum1++;
            if(cur_first<0)
                cur_first=first[o];
        }
    }else{
        if(ql<=L && R<=qr){
            int temp=cur_last;
            cur_last=last[o];
            sum1+=sumv[o];
            if(temp==first[o])
                sum1--;
            if(cur_first<0)
                cur_first=first[o];
        }else{
            DEF_MID;
            if(ql<=M)
                query1(lc,L,M);
            if(qr>M)
                query1(rc,M+1,R);
        }
    }
}
int n;
void update(int l,int r,int value){
    ql=l;
    qr=r;
    v=value;
    update1(1,1,n);
}
int query(int l,int r){
    cur_first=cur_last=-1;
    sum1=0;
    ql=l;
    qr=r;
    query1(1,1,n);
    return sum1;
}
   
// Graph
int frt[maxn],next[maxn*2],to[maxn*2];
int graph_cnt=0;
inline void Add_Edge(int x,int y){
    graph_cnt++;
    next[graph_cnt]=frt[x];
    frt[x]=graph_cnt;
    to[graph_cnt]=y;
}
   
// Heavy Desc
bitset<maxn> vis;
int dep[maxn],fa[maxn],son[maxn],siz[maxn];
void dfs_1(int x,int father,int depth){
    vis[x]=true;
    dep[x]=depth;
    fa[x]=father;
    siz[x]=1;
    int i,temp,max_siz=0;
    for(i=frt[x];i;i=next[i]){
        temp=to[i];
        if(!vis[temp]){
            dfs_1(temp,x,depth+1);
            siz[x]+=siz[temp];
            if(siz[temp]>max_siz){
                max_siz=siz[temp];
                son[x]=temp;
            }
        }
    }
}
int hd_cnt=0;
int tid[maxn],top[maxn],d[maxn];
void dfs_2(int x,int a){
    vis[x]=true;
    top[x]=a;
    tid[x]=++hd_cnt;
    update(hd_cnt,hd_cnt,d[x]);
    if(son[x])
        dfs_2(son[x],a);
    else
        return;
    int i,temp;
    for(i=frt[x];i;i=next[i]){
        temp=to[i];
        if(!vis[temp])
            dfs_2(temp,temp);
    }
}
void change(int x,int y,int value){
    if(top[x]==top[y]){
        if(tid[x]>tid[y])
            swap(x,y);
        update(tid[x],tid[y],value);
        return;
    }
    if(dep[top[x]]<dep[top[y]])
        swap(x,y);
    update(tid[top[x]],tid[x],value);
    change(fa[top[x]],y,value);
}
int get_ans(int x,int y){
    register int ans=0,t1=-1,t2=-1;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]){
            swap(x,y);
            swap(t1,t2);
        }
        ans+=query(tid[top[x]],tid[x]);
        if(t1==cur_last)
            ans--;
        t1=cur_first;
        x=fa[top[x]];
    }
    if(dep[x]<dep[y]){
        swap(x,y);
        swap(t1,t2);
    }
    ans+=query(tid[y],tid[x]);
    if(t1!=-1 && t1==cur_last)
        ans--;
    if(t2!=-1 && t2==cur_first)
        ans--;
    return ans;
}
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[10];
inline void writeint(int x){
    register int p=0;
    if(x==0){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(register int i=p-1;i>=0;i--)
        putchar('0'+bf[i]);
}
int main(){
    register int i;
    register int m,u,v,value;
    char buf[3];
    n=readint();
    m=readint();
    REPB(i,n)
        d[i]=readint();
    REP(i,n-1){
        u=readint();
        v=readint();
        Add_Edge(u,v);
        Add_Edge(v,u);
    }
    memset(setv,-1,sizeof(setv));
    dfs_1(1,0,1);
    vis.reset();
    dfs_2(1,1);
    REP(i,m){
        scanf("%s",buf);
        u=readint();
        v=readint();
        if(buf[0]=='C'){
            value=readint();
            change(u,v,value);
        }else{
            writeint(get_ans(u,v));
            putchar('\n');
        }
    }
    return 0;
}

• 相关文章
• 全局相关文章