LG1505 [国家集训队]旅游 树链剖分

问题描述

LG1505

题解

边化点权。

超级多操作的树剖板子...

以后就拿这个当树剖板子复习吧...

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

template <typename Tp>
void fr(Tp &x){
    char ch=1;
    while(ch!='C'&&ch!='N'&&ch!='S'&&ch!='M') ch=getchar();
    if(ch=='M'){
        ch=1;while(ch!='A'&&ch!='I') ch=getchar();
    }
    if(ch=='C') x=1;
    else if(ch=='N') x=2;
    else if(ch=='S') x=3;
    else if(ch=='A') x=4;
    else x=5;
}

const int maxn=40007;
const int INF=0x3f3f3f3f;

int n;
int Head[maxn],to[maxn],Next[maxn],tot=1,w[maxn];

int size[maxn],fa[maxn],dep[maxn];
int New[maxn],pre[maxn],ind,top[maxn];
int son[maxn];

//edge id i  ->  2*i-1,2*i

void add(int x,int y,int z){
    to[++tot]=y,Next[tot]=Head[x],Head[x]=tot,w[tot]=z;
}

void dfs1(int x,int f,int dp){
    size[x]=1,fa[x]=f,dep[x]=dp;
    int mxx=-1;
    for(int i=Head[x];i;i=Next[i]){
        int y=to[i];
        if(y==f) continue;
        dfs1(y,x,dp+1);
        size[x]+=size[y];
        if(size[y]>mxx) mxx=size[y],son[x]=y;
    }
}

void dfs2(int x,int tp){
    New[x]=++ind,pre[ind]=x,top[x]=tp;
    if(!son[x]) return;
    dfs2(son[x],tp);
    for(int i=Head[x];i;i=Next[i]){
        int y=to[i];
        if(y==fa[x]||y==son[x]) continue;
        dfs2(y,y);
    }
}

int val[maxn],f[maxn];

void preprocess(){ 
    for(int i=2;i<=tot;i+=2){//错误笔记：tot一开始等于1，则第一条边从2开始 
        int x=to[i xor 1],y=to[i];
        if(dep[x]>dep[y]) val[x]=w[i],f[i]=f[i xor 1]=x;//错误笔记：边化点权，要记录每个边化到哪个点上了。 
        else val[y]=w[i],f[i]=f[i xor 1]=y;
    }
}

#define lfc (x<<1)
#define rgc ((x<<1)|1)
#define mid ((l+r)>>1)

int mx[maxn<<1],mi[maxn<<1],sum[maxn<<1];
int lazy[maxn<<1];

void pushup(int x){
    mx[x]=max(mx[lfc],mx[rgc]);
    mi[x]=min(mi[lfc],mi[rgc]);
    sum[x]=sum[lfc]+sum[rgc];
}

void pushdown(int x){
    if(!lazy[x]) return;
    lazy[lfc]^=1,lazy[rgc]^=1;
    sum[lfc]=-sum[lfc],sum[rgc]=-sum[rgc];
    int lf=mx[lfc],rg=mx[rgc];
    mx[lfc]=-mi[lfc],mx[rgc]=-mi[rgc];
    mi[lfc]=-lf,mi[rgc]=-rg;
    lazy[x]=0;//错误笔记：lazy标记有没有清空 
}

void build(int x,int l,int r){
    if(l==r){
        mx[x]=mi[x]=sum[x]=val[pre[l]];
        return;
    }
    build(lfc,l,mid);build(rgc,mid+1,r);
    pushup(x);
}

int L,R,need;

void dd_change(int x,int l,int r){
    if(l==r&&L==l){
        sum[x]=mx[x]=mi[x]=need;return;
    }
    pushdown(x);
    if(L<=mid) dd_change(lfc,l,mid);
    else dd_change(rgc,mid+1,r);
    pushup(x);
}

void qj_change(int x,int l,int r){
    if(l>R||r<L) return;
    if(L<=l&&r<=R){
        lazy[x]^=1;int temp=mx[x];
        sum[x]=-sum[x],mx[x]=-mi[x],mi[x]=-temp;
        return;
    }
    pushdown(x);
    qj_change(lfc,l,mid);qj_change(rgc,mid+1,r);
    pushup(x);
}

int sum_query(int x,int l,int r){
    if(l>R||r<L) return 0;
    if(L<=l&&r<=R) return sum[x];
    pushdown(x);
    return sum_query(lfc,l,mid)+sum_query(rgc,mid+1,r);
}

int max_query(int x,int l,int r){
    if(l>R||r<L) return -INF;
    if(L<=l&&r<=R) return mx[x];
    pushdown(x);
    return max(max_query(lfc,l,mid),max_query(rgc,mid+1,r));
}

int min_query(int x,int l,int r){
    if(l>R||r<L) return INF;
    if(L<=l&&r<=R) return mi[x];
    pushdown(x);
    return min(min_query(lfc,l,mid),min_query(rgc,mid+1,r));
}

int T,op;

void cz1(){
    int x;
    read(x);read(need);
    x=New[f[x<<1]],L=x;//错误笔记：双向存边，在数组中编号要*2 
    dd_change(1,1,n);
}

void cz2(){
    int x,y;
    read(x);read(y);
    ++x,++y;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        L=New[top[x]],R=New[x];//错误笔记：写作L=New[x],R=New[y] 
        qj_change(1,1,n);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    L=New[x]+1,R=New[y];
    if(L<=R) qj_change(1,1,n);
}

void cz3(){
    int x,y,res=0;
    read(x);read(y);
    ++x,++y;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        L=New[top[x]],R=New[x];
        res+=sum_query(1,1,n);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    L=New[x]+1,R=New[y];
    if(L<=R) res+=sum_query(1,1,n);
    printf("%d\n",res);
}

void cz4(){
    int x,y,res=-INF;
    read(x);read(y);
    ++x,++y;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        L=New[top[x]],R=New[x];
        res=max(res,max_query(1,1,n));
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    L=New[x]+1,R=New[y];
    if(L<=R) res=max(res,max_query(1,1,n));
    printf("%d\n",res);
}

void cz5(){
    int x,y,res=INF;
    read(x);read(y);
    ++x,++y;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        L=New[top[x]],R=New[x];
        res=min(res,min_query(1,1,n));
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    L=New[x]+1,R=New[y];
    if(L<=R) res=min(res,min_query(1,1,n));
    printf("%d\n",res);
}

int main(){
    #ifndef ONLINE_JUDGE
        freopen("travel.in","r",stdin);
    #endif
    read(n);
    for(int i=1,x,y,z;i<n;i++){
        read(x);read(y);read(z);
        ++x,++y;
        add(x,y,z);add(y,x,z);
    }
    dfs1(1,0,1);dfs2(1,1);
    preprocess();build(1,1,n);
    read(T);
    while(T--){
        fr(op);
        if(op==1) cz1();
        else if(op==2) cz2();
        else if(op==3) cz3();
        else if(op==4) cz4();
        else cz5();
    }
    return 0;
}