企网站的互联网,四川省安监站网址,承德项目网,东阳实惠营销型网站建设LOJ2195 旅行 题目描述S 国有 N 个城市#xff0c;编号从 1 到 N。城市间用 N-1 条双向道路连接#xff0c;满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教#xff0c;如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便#xff0c;我们用不…LOJ2195 旅行 题目描述S 国有 N 个城市编号从 1 到 N。城市间用 N-1 条双向道路连接满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便我们用不同的正整数代表各种宗教S 国境内总共有 c 种不同的宗教。 S 国的居民常常旅行。旅行时他们总会走最短路并且为了避免麻烦只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S 国政府为每个城市标定了不同的旅行评级旅行者们常会记下途中包括起点和终点留宿过的城市的评级总和或最大值。 在 S 国的历史上常会发生以下几种事件 CC x c城市 x 的居民全体改信了 c 教CW x w城市 x 的评级调整为 wQS x y一位旅行者从城市 x 出发到城市 y并记下了途中留宿过的城市的评级总和QM x y一位旅行者从城市 x 出发到城市 y并记下了途中留宿过的城市的评级最大值。由于年代久远旅行者记下的数字已经遗失了但记录开始之前每座城市的信仰与评级还有事件记录本身是完好的。请根据这些信息还原旅行者记下的数字。为了方便我们认为事件之间的间隔足够长以致在任意一次旅行中所有城市的评级和信仰保持不变。 输入格式输入的第一行包含整数 NQ 依次表示城市数和事件数。接下来 N 行第 i1 行两个整数 WiCi 依次表示记录开始之前城市 i 的评级和信仰。接下来 N-1 行每行两个整数 xy 表示一条双向道路。接下来 Q 行每行一个操作格式如上所述。 输出格式对每个 QS 和 QM 事件输出一行表示旅行者记下的数字。 样例样例输入5 63 12 31 23 35 11 21 33 43 5QS 1 5CC 3 1QS 1 5CW 3 3QS 1 5QM 2 4样例输出8913数据范围与提示对所有的数据N,Q≤10^5, C≤10^5对所有 QS 和 QM 事件起点和终点城市的信仰相同在任意时刻城市的评级总是不大于 10^4 的正整数且宗教值不大于 c。 _________________________________________________________________________________________ 树链剖分单点修改求和。 但是由于只对对应的点信奉相同的宗教的点求和而宗教的种类太多每个线段树的点不能为10^5个点所以要动态开点。 第一次写动态开点线段树但过去用指针写过线段树所以感觉不算难。 所谓动态开点就是用不到的点先不要建点只把对应的点建立这样每次建一个点只需要建一条链长logn就可以了不用的点先不用建。 其他的和普通线段树一样。 _________________________________________________________________________________________ 1 #includebits/stdc.h2 using namespace std;3 typedef int ll;4 const ll maxn1e510;5 ll n,m;6 struct edge7 {8 int u,v,nxt;9 }e[maxn1];10 ll head[maxn],js;11 void addage(ll u,ll v)12 {13 e[js].uu;e[js].vv;14 e[js].nxthead[u];head[u]js;15 }16 ll w[maxn],c[maxn];17 ll dep[maxn],fat[maxn],siz[maxn],son[maxn];18 void dfs(ll u,ll fa)19 {20 dep[u]dep[fa]1;21 fat[u]fa;22 siz[u]1;23 for(ll ihead[u];i;ie[i].nxt)24 {25 ll ve[i].v;26 if(vfa)continue;27 dfs(v,u);28 siz[u]siz[v];29 if(!son[u] || siz[son[u]]siz[v])son[u]v;30 }31 }32 ll p,pos[maxn],fos[maxn],top[maxn];33 void getpos(ll u,ll fa)34 {35 pos[u]p;36 fos[p]u;37 top[u]fa;38 if(!son[u])return ;39 getpos(son[u],fa);40 for(ll ihead[u];i;ie[i].nxt)41 {42 ll ve[i].v;43 if(v!fat[u] v!son[u])getpos(v,v);44 }45 }46 struct node47 {48 int lc,rc,sm,mx;49 }t[2001000];50 int rt[maxn],cnt;51 void update(ll cur)52 {53 t[cur].smt[t[cur].lc].smt[t[cur].rc].sm;54 t[cur].mxmax(t[t[cur].lc].mx,t[t[cur].rc].mx);55 }56 void change(ll cur,ll l,ll r,ll p,ll x)57 {58 if(!cur)curcnt;59 if(lr)60 {61 t[cur].smt[cur].mxx;62 return ;63 }64 ll mid(lr)1;65 if(pmid)change(t[cur].lc,l,mid,p,x);66 else change(t[cur].rc,mid1,r,p,x);67 update(cur);68 }69 ll SUM,MAX;70 void query(ll cur,ll l,ll r,ll ql,ll qr)71 {72 if(!cur)return ;73 if(qll rqr)74 {75 SUMt[cur].sm;76 MAXmax(MAX,t[cur].mx);77 return ;78 }79 ll mid(lr)1;80 if(qlmid)query(t[cur].lc,l,mid,ql,qr);81 if(midqr)query(t[cur].rc,mid1,r,ql,qr);82 }83 void ask(ll u,ll v)84 {85 SUM0;MAX0;86 ll clc[u];87 ll tputop[u],tpvtop[v];88 while(tpu!tpv)89 {90 if(dep[tpu]dep[tpv])91 {92 swap(u,v);93 swap(tpu,tpv);94 }95 query(rt[cl],1,n,pos[tpu],pos[u]);96 ufat[tpu];tputop[u];97 }98 if(dep[u]dep[v])swap(u,v);99 query(rt[cl],1,n,pos[u],pos[v]);
100 }
101 int main()
102 {
103 scanf(%d%d,n,m);
104 for(ll i1;in;i)scanf(%d%d,wi,ci);
105 for(ll u,v,i1;in;i)
106 {
107 scanf(%d%d,u,v);
108 addage(u,v);addage(v,u);
109 }
110 dfs(1,0);
111 getpos(1,1);
112 for(ll i1;in;i)change(rt[c[i]],1,n,pos[i],w[i]);
113 char s[4];
114 ll u,v;
115 while(m--)
116 {
117 scanf(%s%d%d,s,u,v);
118 if(s[1]W)
119 {
120 w[u]v;
121 change(rt[c[u]],1,n,pos[u],v);
122 }
123 else if(s[1]C)
124 {
125 change(rt[c[u]],1,n,pos[u],0);
126 c[u]v;
127 change(rt[c[u]],1,n,pos[u],w[u]);
128 }
129 else if(s[1]S)
130 {
131 ask(u,v);
132 printf(%d\n,SUM);
133 }
134 else
135 {
136 ask(u,v);
137 printf(%d\n,MAX);
138 }
139 }
140 return 0;
141 } View Code 转载于:https://www.cnblogs.com/gryzy/p/10479157.html
