3531: [Sdoi2014]旅行
Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 837 Solved: 426
[Submit][Status][Discuss]
Description
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,并记下了途中留宿过
的城市的评级最大值。
由于年代久远,旅行者记下的数字已经遗失了,但记录开始之前每座城市的信仰与评级,还有事件记录本身是完好的。请根据这些信息,还原旅行者记下的数字。 为了方便,我们认为事件之间的间隔足够长,以致在任意一次旅行中,所有城市的评级和信仰保持不变。
Input
输入的第一行包含整数N,Q依次表示城市数和事件数。
接下来N行,第i+l行两个整数Wi,Ci依次表示记录开始之前,城市i的
评级和信仰。
接下来N-1行每行两个整数x,y表示一条双向道路。
接下来Q行,每行一个操作,格式如上所述。
Output
对每个QS和QM事件,输出一行,表示旅行者记下的数字。
Sample Input
Sample Output
HINT
N,Q < =10^5 , C < =10^5
数据保证对所有QS和QM事件,起点和终点城市的信仰相同;在任意时
刻,城市的评级总是不大于10^4的正整数,且宗教值不大于C。
Source
在普通的树链剖分基础上加了一个宗教的限制,但我们发现宗教个数在105范围内,我们可以对每个宗教开一个线段树,然后只要访问到的点开点就可以了,这样就不会超内存了。挺水的
代码:
#include<cstdio> #include<algorithm> using namespace std; struct node{int l,r,sum,max;}tr[10000010]; int n,q,edgenum,u,v,tot,cnt,x,y,z,ans; int f[200010],d[200010],num[200010],son[200010],top[200010],tid[200010],pre[200010],root[200010]; int vet[200010],next[200010],head[200010],w[200010],c[200010]; char opt[20]; void add(int u,int v) { vet[++edgenum]=v; next[edgenum]=head[u]; head[u]=edgenum; } void dfs(int u,int fa,int dep) { f[u]=fa; d[u]=dep; num[u]=1; int maxnum=0; for (int e=head[u];e;e=next[e]) { int v=vet[e]; if (v!=fa) { dfs(v,u,dep+1); num[u]+=num[v]; if (num[v]>maxnum){maxnum=num[v];son[u]=v;} } } } void dfs(int u,int number) { top[u]=number; tid[u]=++tot; pre[tot]=u; if (!son[u]) return; dfs(son[u],number); for (int e=head[u];e;e=next[e]) { int v=vet[e]; if (v!=f[u]&&v!=son[u]) dfs(v,v); } } int lca(int u,int v) { for (;top[u]!=top[v];u=f[top[u]])if (d[top[u]]<d[top[v]]) swap(u,v); if (d[u]<d[v]) return u;return v; } void change(int l,int r,int &p,int x,int val) { if (!p) p=++cnt; if (l==r){tr[p].max=tr[p].sum=val;return;} int mid=(l+r)>>1; if (x<=mid) change(l,mid,tr[p].l,x,val);else change(mid+1,r,tr[p].r,x,val); tr[p].max=max(tr[tr[p].l].max,tr[tr[p].r].max); tr[p].sum=tr[tr[p].l].sum+tr[tr[p].r].sum; } int askmax(int l,int r,int p,int x,int y) { if (!p) return 0; if (l==x&&y==r) return tr[p].max; int mid=(l+r)>>1; if (y<=mid) return askmax(l,mid,tr[p].l,x,y);else if (x>mid) return askmax(mid+1,r,tr[p].r,x,y);else return max(askmax(l,mid,tr[p].l,x,mid),askmax(mid+1,r,tr[p].r,mid+1,y)); } int asksum(int l,int r,int p,int x,int y) { if (!p) return 0; if (l==x&&y==r) return tr[p].sum; int mid=(l+r)>>1; if (y<=mid) return asksum(l,mid,tr[p].l,x,y);else if (x>mid) return asksum(mid+1,r,tr[p].r,x,y);else return asksum(l,mid,tr[p].l,x,mid)+asksum(mid+1,r,tr[p].r,mid+1,y); } int getsum(int u,int v,int c) { int ans=0; while (top[u]!=top[v]) { ans+=asksum(1,n,root[c],tid[top[u]],tid[u]); u=f[top[u]]; } ans+=asksum(1,n,root[c],tid[v],tid[u]); return ans; } int getmax(int u,int v,int c) { int ans=0; while (top[u]!=top[v]) { ans=max(ans,askmax(1,n,root[c],tid[top[u]],tid[u])); u=f[top[u]]; } ans=max(ans,askmax(1,n,root[c],tid[v],tid[u])); return ans; } 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;i<n;i++) { scanf("%d%d",&u,&v); add(u,v);add(v,u); } dfs(1,0,1); dfs(1,1); for (int i=1;i<=n;i++) change(1,n,root[c[i]],tid[i],w[i]); while (q--) { scanf("%s",opt); scanf("%d%d",&x,&y); if (opt[0]=='C') { if (opt[1]=='C') { change(1,n,root[c[x]],tid[x],0); c[x]=y; change(1,n,root[c[x]],tid[x],w[x]); }else {change(1,n,root[c[x]],tid[x],y);w[x]=y;} }else { z=lca(x,y); if (opt[1]=='S') { ans=getsum(x,z,c[x])+getsum(y,z,c[x]); if (c[x]==c[z]) ans-=w[z]; printf("%d\n",ans); }else printf("%d\n",max(getmax(x,z,c[x]),getmax(y,z,c[x]))); } } }