BZOJ 3531 [Sdoi2014]旅行 树链剖分+动态开点线段树

题意

S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。

为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。

在S国的历史上常会发生以下几种事件：

“CC x c“：城市x的居民全体改信了c教；

“CW x w“：城市x的评级调整为w;

“QS x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；

“QM x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级最大值。

由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。 为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

分析

对每种宗教建一颗动态开点线段树，不动态开点稳Tle+Mle的，然后就树链剖分裸题啊，对于查询操作，查询出发城市的信仰宗教的线段树就行了

这题写完就过编译和样例了，然后在bzoj一交秒Tle??内存636kb？？感觉数据有问题去洛谷交了下，一发过!

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
using namespace std;
typedef long long ll;
const int inf=1e9;
const int maxn=2e5;
int n,q;
int w[maxn],c[maxn];
vector<int>g[maxn];
int sz[maxn],son[maxn],top[maxn],p[maxn],d[maxn],f[maxn],id[maxn],tot;
int val[maxn*300],mx[maxn*300],ls[maxn*300],rs[maxn*300],rt[maxn],o;
void up(int x,int l,int r,int &p,int k){
    val[++o]=val[p],mx[o]=mx[p],ls[o]=ls[p],rs[o]=rs[p],p=o;
    if(l==r) return val[p]=mx[p]=k,void();
    int mid=l+r>>1;
    if(x<=mid) up(x,l,mid,ls[p],k);
    else up(x,mid+1,r,rs[p],k);
    val[p]=val[ls[p]]+val[rs[p]];
    mx[p]=max(mx[ls[p]],mx[rs[p]]);
}
int qy(int dl,int dr,int l,int r,int p){
    if(l>=dl&&r<=dr) return val[p];
    int mid=l+r>>1;int ret=0;
    if(dl<=mid) ret+=qy(dl,dr,l,mid,ls[p]);
    if(dr>mid) ret+=qy(dl,dr,mid+1,r,rs[p]);
    return ret;
}
int qmx(int dl,int dr,int l,int r,int p){
    if(l>=dl&&r<=dr) return mx[p];
    int mid=l+r>>1;int ret=-inf;
    if(dl<=mid) ret=max(qmx(dl,dr,l,mid,ls[p]),ret);
    if(dr>mid) ret=max(qmx(dl,dr,mid+1,r,rs[p]),ret);
    return ret;
}
void dfs1(int u){
    sz[u]=1;d[u]=d[f[u]]+1;
    for(int i=0;i<g[u].size();i++){
        int x=g[u][i];
        if(x==f[u]) continue;
        f[x]=u;dfs1(x);
        sz[u]+=sz[x];
        if(sz[x]>sz[son[u]]) son[u]=x;
    }
}
void dfs2(int u,int t){
    top[u]=t;p[u]=++tot;id[tot]=u;
    if(son[u]) dfs2(son[u],t);
    for(int i=0;i<g[u].size();i++){
        int x=g[u][i];
        if(x==f[u]||x==son[u]) continue;
        dfs2(x,x);
    }
}
int cals(int x,int y,int r){
    int ret=0;
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]]) swap(x,y);
        ret+=qy(p[top[x]],p[x],1,n,rt[r]);
        x=f[top[x]];
    }
    if(d[x]<d[y]) swap(x,y);
    return ret+qy(p[y],p[x],1,n,rt[r]);
}
int calx(int x,int y,int r){
    int ret=-inf;
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]]) swap(x,y);
        ret=max(ret,qmx(p[top[x]],p[x],1,n,rt[r]));
        x=f[top[x]];
    }
    if(d[x]<d[y]) swap(x,y);
    return max(ret,qmx(p[y],p[x],1,n,rt[r]));
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&w[i],&c[i]);
    }
    for(int i=1,a,b;i<n;i++){
        scanf("%d%d",&a,&b);
        g[a].pb(b);g[b].pb(a);
    }
    dfs1(1);dfs2(1,1);
    for(int i=1;i<=n;i++){
        up(p[i],1,n,rt[c[i]],w[i]);
    }
    while(q--){
        char s[20];
        int x,y,cc,ww;
        scanf("%s",s);
        if(s[1]=='C'){
            scanf("%d%d",&x,&cc);
            up(p[x],1,n,rt[c[x]],0);
            c[x]=cc;
            up(p[x],1,n,rt[c[x]],w[x]);
        }else if(s[1]=='W'){
            scanf("%d%d",&x,&ww);
            w[x]=ww;
            up(p[x],1,n,rt[c[x]],w[x]);
        }else if(s[1]=='S'){
            scanf("%d%d",&x,&y);
            printf("%d\n",cals(x,y,c[x]));
        }else{
            scanf("%d%d",&x,&y);
            printf("%d\n",calx(x,y,c[x]));
        }
    }
    return 0;
}

BZOJ 3531 [Sdoi2014]旅行 树链剖分+动态开点线段树

原文：https://www.cnblogs.com/xyq0220/p/10915061.html