树剖入门题 洛谷P3313 [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，并记下了途中留宿过的城市的评级最大值。

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

输入格式
输入的第一行包含整数N，Q依次表示城市数和事件数。

接下来N行，第i+l行两个整数Wi，Ci依次表示记录开始之前，城市i的评级和信仰。 接下来N-1行每行两个整数x，y表示一条双向道路。

接下来Q行，每行一个操作，格式如上所述。

输出格式
对每个QS和QM事件，输出一行，表示旅行者记下的数字。

输入输出样例
输入
5 6
3 1
2 3
1 2
3 3
5 1
1 2
1 3
3 4
3 5
QS 1 5
CC 3 1
QS 1 5
CW 3 3
QS 1 5
QM 2 4
输出
8
9
11
3

这题一眼过去你会发现其实跟树剖板子没啥区别，就是多了个约束宗教信仰，我们很自然的能想到对每个宗教都开个线段树来做，但因为会爆空间，所以要动态开点，完美的把空间降到了$O(nlog)$级别，其余就按板子打就是了。
code：

#include
using namespace std;
const int N=1e5+10;
int n,q,x,y,w[N],c[N],tot,first[N],Next[N*2],to[N*2];
int mson[N],zx[N],id[N],index_,dep[N],f[N],siz[N];
int ls[N*40],rs[N*40],val1[N*40],val2[N*40],cnt,rt[N];
string saber;
int Read()
{int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return f*x;
}
void add(int a,int b)
{tot++;Next[tot]=first[a];first[a]=tot;to[tot]=b;
}
void dfs1(int u,int fa)
{int Max=0;for(int i=first[u];i;i=Next[i]){int v=to[i];if(v==fa) continue;dep[v]=dep[u]+1;f[v]=u;dfs1(v,u);siz[u]+=siz[v];if(Max<siz[v]) Max=siz[v],mson[u]=v;}
}
void dfs2(int u,int zz)
{id[u]=++index_;zx[u]=zz;if(mson[u]) dfs2(mson[u],zz);for(int i=first[u];i;i=Next[i]){int v=to[i];if(v==f[u]||v==mson[u]) continue;dfs2(v,v);}
}
void pushup(int u)
{val1[u]=max(val1[ls[u]],val1[rs[u]]);val2[u]=val2[ls[u]]+val2[rs[u]];
}
void update(int &u,int l,int r,int pos,int val)
{if(!u) u=++cnt;if(l==r){val1[u]=val2[u]=val;return;}int mid=(l+r)>>1;if(pos<=mid) update(ls[u],l,mid,pos,val);else update(rs[u],mid+1,r,pos,val);pushup(u);
}
void Delete(int u,int l,int r,int pos)
{if(l==r){val1[u]=val2[u]=0;return;}int mid=(l+r)>>1;if(pos<=mid) Delete(ls[u],l,mid,pos);else Delete(rs[u],mid+1,r,pos);pushup(u);
}
int query1(int u,int l,int r,int op,int ed)
{if(l>=op&&r<=ed) return val1[u];int Max=0;int mid=(l+r)>>1;if(op<=mid) Max=max(Max,query1(ls[u],l,mid,op,ed));if(ed>mid) Max=max(Max,query1(rs[u],mid+1,r,op,ed));return Max;
}
int query2(int u,int l,int r,int op,int ed)
{if(l>=op&&r<=ed) return val2[u];int sum=0;int mid=(l+r)>>1;if(op<=mid) sum+=query2(ls[u],l,mid,op,ed);if(ed>mid) sum+=query2(rs[u],mid+1,r,op,ed);return sum;
}
int Query1(int u,int v,int col)
{int Max=0;while(zx[u]!=zx[v]){if(dep[zx[u]]<dep[zx[v]]) swap(u,v);Max=max(Max,query1(rt[col],1,n,id[zx[u]],id[u]));u=f[zx[u]];}if(dep[u]>dep[v]) swap(u,v);Max=max(Max,query1(rt[col],1,n,id[u],id[v]));return Max;
}
int Query2(int u,int v,int col)
{int sum=0;while(zx[u]!=zx[v]){if(dep[zx[u]]<dep[zx[v]]) swap(u,v);sum+=query2(rt[col],1,n,id[zx[u]],id[u]);u=f[zx[u]];}if(dep[u]>dep[v]) swap(u,v);sum+=query2(rt[col],1,n,id[u],id[v]);return sum;
}
int main()
{n=Read(),q=Read();for(int i=1;i<=n;i++) w[i]=Read(),c[i]=Read(),siz[i]=1;for(int i=1;i<n;i++){x=Read(),y=Read();add(x,y),add(y,x);}dfs1(1,0),dfs2(1,1);for(int i=1;i<=n;i++) update(rt[c[i]],1,n,id[i],w[i]);for(int i=1;i<=q;i++){cin>>saber,x=Read(),y=Read();//	cout<if(saber=="CC") Delete(rt[c[x]],1,n,id[x]),update(rt[y],1,n,id[x],w[x]),c[x]=y;if(saber=="CW")Delete(rt[c[x]],1,n,id[x]),update(rt[c[x]],1,n,id[x],y),w[x]=y;if(saber=="QS")printf("%d\n",Query2(x,y,c[x]));if(saber=="QM")printf("%d\n",Query1(x,y,c[x]));}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！