洛谷 P3313 [SDOI2014]旅行

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

89113

说明

N，Q < =10^5 ， C < =10^5

数据保证对所有QS和QM事件，起点和终点城市的信仰相同；在任意时

刻，城市的评级总是不大于10^4的正整数，且宗教值不大于C。

思路：动态开节点线段树+树链剖分。有几个宗教就开几棵线段树。

错因：1.区间查询位置分段式第三个应改为mid。

　　　2.数组开得太大，动态开节点线段树应把数组开为logN*N;

#include
#include
#include
#include
#define MAXN 100001
using namespace std;
int n,m,sz,tot,cnt;
int to[MAXN*2],net[MAXN*2],head[MAXN*2];
int religion[MAXN],val[MAXN],root[MAXN];
int id[MAXN],dad[MAXN],top[MAXN],size[MAXN],deep[MAXN];
int sum[MAXN*10*4],maxn[MAXN*10*4],lchild[MAXN*10*4],rchild[MAXN*4*10]; 
void add(int u,int v){to[++tot]=v;net[tot]=head[u];head[u]=tot;to[++tot]=u;net[tot]=head[v];head[v]=tot;
}
void dfs(int x){size[x]=1;deep[x]=deep[dad[x]]+1;for(int i=head[x];i;i=net[i])if(dad[x]!=to[i]){dad[to[i]]=x;dfs(to[i]);size[x]+=size[to[i]];}
}
void dfs1(int x){int t=0;id[x]=++sz;if(!top[x])        top[x]=x;for(int i=head[x];i;i=net[i])if(dad[x]!=to[i]&&size[t]<size[to[i]])t=to[i];if(t){top[t]=top[x];dfs1(t);}for(int i=head[x];i;i=net[i])if(dad[x]!=to[i]&&t!=to[i])dfs1(to[i]);
}
void up(int now){sum[now]=sum[lchild[now]]+sum[rchild[now]];maxn[now]=max(maxn[lchild[now]],maxn[rchild[now]]);
}
void change(int & now,int l,int r,int x,int opt){if(!now)    now=++cnt;if(l==r){sum[now]=maxn[now]=opt;return ;}int mid=(l+r)/2;if(x<=mid)    change(lchild[now],l,mid,x,opt);else if(x>mid)    change(rchild[now],mid+1,r,x,opt);up(now);
}
int query(int now,int l,int r,int xl,int xr,int opt){if(xl==l&&xr==r){if(opt==0)    return sum[now];else return maxn[now];}int mid=(l+r)/2;if(xr<=mid)    return query(lchild[now],l,mid,xl,xr,opt);else if(xl>mid)    return query(rchild[now],mid+1,r,xl,xr,opt);else{if(opt==0)    return query(lchild[now],l,mid,xl,mid,opt)+query(rchild[now],mid+1,r,mid+1,xr,opt);else return max(query(lchild[now],l,mid,xl,mid,opt),query(rchild[now],mid+1,r,mid+1,xr,opt));}
}
int squery(int q,int x,int y,int opt){int ans=0;while(top[x]!=top[y]){if(deep[top[x]]<deep[top[y]])    swap(x,y);if(opt==0)    ans+=query(root[q],1,n,id[top[x]],id[x],opt);else    ans=max(ans,query(root[q],1,n,id[top[x]],id[x],opt));x=dad[top[x]];}if(id[x]>id[y])    swap(x,y);if(opt==0)    ans+=query(root[q],1,n,id[x],id[y],opt);else ans=max(ans,query(root[q],1,n,id[x],id[y],opt));return ans;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d%d",&val[i],&religion[i]);for(int i=1;i){int x,y;scanf("%d%d",&x,&y);add(x,y);}dfs(1);dfs1(1);for(int i=1;i<=n;i++)change(root[religion[i]],1,n,id[i],val[i]);for(int i=1;i<=m;i++){char c[3];int x,y;scanf("%s",c);scanf("%d%d",&x,&y);if(c[0]=='C'){if(c[1]=='W'){change(root[religion[x]],1,n,id[x],y);val[x]=y;    }else{    change(root[religion[x]],1,n,id[x],0);religion[x]=y;change(root[religion[x]],1,n,id[x],val[x]);}}else{if(c[1]=='S')    cout<0)<<endl;    else    cout<1)<<endl;}}
}

转载于:https://www.cnblogs.com/cangT-Tlan/p/7486524.html

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