Luogu p3313 [sdoi2014] Travel Solution

Portal ：[P3313 [SDOI2014] travel ]

$10^5$ Dynamic opening point of a segment tree + The tree chain splits

I'll write the detailed ideas later Attention to detail

–update–

Use the line segment tree writing method of dynamic open points to build the line segment tree of each belief . Press $\text{dfs}$ Order to store （ Corresponding to $\text{dfn}$ Array ）.

use $update$ Function to update the value in the segment tree , Because it's a single point of modification , So no need $pushdown$ operation , and $pushup$ it is desirable that .

When $update$ In the process, it is found that the direction that needs recursion has no child nodes , We'll start with $\text{sgt}$ Apply for a child node in the array , Then continue to recurse downward .

• When you encounter the operation of modifying faith , take $c_x$ On the tree of belief segment $x$ The node is set to $0$, And then $y$ On the tree of belief segment $x$ The node is updated to $w_x$.
• When it comes to modifying the rating , Direct will $c_x$ On the line tree $x$ The node is updated to $w$.
• When querying, directly insert the tree chain and divide it into dfs Use the segment tree to query the sequence .

Accepted code

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

#define maxn 100005
#pragma gcc optimize(2)
int n,q;
string opt;

struct node{
    
    int l,r,sum,max;
}sgt[maxn*32*32];

vector<int>mp[maxn];
int w[maxn],c[maxn];

int fa[maxn],sz[maxn],dep[maxn],dfn[maxn],son[maxn],top[maxn];

void dfs1(int u,int f,int d){
    
    fa[u]=f;
    dep[u]=d;
    sz[u]=1;
    son[u]=0;
    sz[son[u]]=0;
    for(auto v:mp[u]){
    
        if(v==f) continue;
        dfs1(v,u,d+1);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]]) son[u]=v;
    }
}
int tot=0;
void dfs2(int u,int f,int t){
    
    top[u]=t;
    dfn[u]=++tot;
    if(son[u]){
    
        dfs2(son[u],u,t);
        for(auto v:mp[u]){
    
            if(v==f) continue;
            if(v==son[u]) continue;
            dfs2(v,u,v);
        }
    }
}

void pushup(int d){
    
    sgt[d].sum=0,sgt[d].max=0;
    if(sgt[d].l){
    
        sgt[d].max=max(sgt[d].max,sgt[sgt[d].l].max);
        sgt[d].sum=sgt[d].sum+sgt[sgt[d].l].sum;
    }
    if(sgt[d].r){
    
        sgt[d].max=max(sgt[d].max,sgt[sgt[d].r].max);
        sgt[d].sum=sgt[d].sum+sgt[sgt[d].r].sum;
    }
}

int cnt=maxn;

void update(int d,int pos,int val,int l,int r){
    
    if(l==r){
    
        sgt[d].sum=sgt[d].max=val;
        return ;
    }
    int mid=l+r>>1;
    if(pos<=mid){
    
        if(!sgt[d].l) sgt[d].l=++cnt;
        update(sgt[d].l,pos,val,l,mid);
    }else{
    
        if(!sgt[d].r) sgt[d].r=++cnt;
        update(sgt[d].r,pos,val,mid+1,r);
    }
    pushup(d);
}

int query(int d,int x,int y,int l,int r,int ver){
    
    if(x<=l&&r<=y) return ver?sgt[d].max:sgt[d].sum;
    int mid=l+r>>1;
    int ret=0;
    if(x<=mid&&sgt[d].l) ret=(ver?max(ret,query(sgt[d].l,x,y,l,mid,ver)):ret+query(sgt[d].l,x,y,l,mid,ver));
    if(y>mid&&sgt[d].r) ret=(ver?max(ret,query(sgt[d].r,x,y,mid+1,r,ver)):ret+query(sgt[d].r,x,y,mid+1,r,ver));
    return ret;
}

void init(){
    
    for(int i=1;i<=n;i++){
    
        update(c[i],dfn[i],w[i],1,n);
    }
}

int query(int x,int y,int ver){
    
    int color=c[x];
    int ret=0;
    while(top[x]!=top[y]){
    
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        if(ver) ret=max(ret,query(color,dfn[top[x]],dfn[x],1,n,ver));
        else ret=ret+query(color,dfn[top[x]],dfn[x],1,n,ver);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    if(ver) ret=max(ret,query(color,dfn[x],dfn[y],1,n,ver));
    else ret=ret+query(color,dfn[x],dfn[y],1,n,ver);
    return ret;
}

int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
    
        cin>>w[i]>>c[i];
    }
    for(int i=1,u,v;i<=n-1;i++){
    
        cin>>u>>v;
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    dfs1(1,0,1);
    dfs2(1,0,1);
    init();
    int x,y;
    while(q--){
    
        cin>>opt;
        if(opt=="CC"){
    
            cin>>x>>y;
            update(c[x],dfn[x],0,1,n);
            update(y,dfn[x],w[x],1,n);
            c[x]=y;
        }else if(opt=="CW"){
    
            cin>>x>>y;
            update(c[x],dfn[x],y,1,n);
            w[x]=y;
        }else if(opt=="QS"){
    
            cin>>x>>y;
            cout<<query(x,y,0)<<'\n';
        }else if(opt=="QM"){
    
            cin>>x>>y;
            cout<<query(x,y,1)<<'\n';
        }
    }
}