怎么做网站自动响应,广州建设交易中心,深圳建筑设计公司,重庆交通大学官网网站Description 给定一棵有n个节点的无根树和m个操作#xff0c;操作有2类#xff1a; 1、将节点a到节点b路径上所有点都染成颜色c#xff1b; 2、询问节点a到节点b路径上的颜色段数量#xff08;连续相同颜色被认为是同一段#xff09;#xff0c;如“112221”由3段组成操作有2类 1、将节点a到节点b路径上所有点都染成颜色c 2、询问节点a到节点b路径上的颜色段数量连续相同颜色被认为是同一段如“112221”由3段组成“11”、“222”和“1”。 请你写一个程序依次完成这m个操作。 Input 第一行包含2个整数n和m分别表示节点数和操作数 第二行包含n个正整数表示n个节点的初始颜色 下面 行每行包含两个整数x和y表示x和y之间有一条无向边。 下面 行每行描述一个操作 “C a b c”表示这是一个染色操作把节点a到节点b路径上所有点包括a和b都染成颜色c “Q a b”表示这是一个询问操作询问节点a到节点b包括a和b路径上的颜色段数量。 Output 对于每个询问操作输出一行答案。 Sample Input 6 5 2 2 1 2 1 1 1 2 1 3 2 4 2 5 2 6 Q 3 5 C 2 1 1 Q 3 5 C 5 1 2 Q 3 5 Sample Output 3 1 2 HINT 数N10^5操作数M10^5所有的颜色C为整数且在[0, 10^9]之间。 【分析】 还是树链剖分主要是线段树那里要记录最左边的颜色和最右边的颜色合并的时候看看中间相接部分颜色是否相同如果相同ans-1. 询问的时候是要重链、轻边的跳的也是要记录左右的颜色判断颜色是否相同。 代码如下 1 #includecstdio2 #includecstdlib3 #includecstring4 #includeiostream5 #includealgorithm6 using namespace std;7 #define Maxn 1000108 9 struct node10 {11 int x,y,next;12 }t[2*Maxn];int len0;13 14 int c[Maxn],fa[Maxn],size[Maxn],first[Maxn],dep[Maxn];15 int top[Maxn],w[Maxn],son[Maxn];16 int wl0;17 18 void ins(int x,int y)19 {20 t[len].xx;t[len].yy;21 t[len].nextfirst[x];first[x]len;22 }23 24 struct nnode25 {26 int l,r,lc,rc,cl,cr,sum,lazy;27 }tr[2*Maxn];int tl0;28 29 void dfs1(int x,int f)30 {31 dep[x]dep[f]1;32 size[x]1;fa[x]f;son[x]0;33 for(int ifirst[x];i;it[i].next) if(t[i].y!f)34 {35 dfs1(t[i].y,x);36 size[x]size[t[i].y];37 if(size[t[i].y]size[son[x]]) son[x]t[i].y;38 }39 }40 41 void dfs2(int x,int tp)42 {43 top[x]tp;w[x]wl;44 if(size[x]!1) dfs2(son[x],tp);45 for(int ifirst[x];i;it[i].next) if(t[i].y!fa[x]t[i].y!son[x])46 {47 dfs2(t[i].y,t[i].y);48 }49 }50 51 int build(int l,int r)52 {53 int xtl;54 tr[x].ll;tr[x].rr;tr[x].lazy-1;tr[x].sum0;55 if(l!r)56 {57 int mid(lr)1;58 tr[x].lcbuild(l,mid);59 tr[x].rcbuild(mid1,r);60 }61 return x;62 }63 64 void upd(int x)65 {66 if(tr[x].lazy-1) return;67 tr[x].sum1;tr[x].cltr[x].crtr[x].lazy;68 if(tr[x].l!tr[x].r)69 {70 tr[tr[x].lc].lazytr[x].lazy;71 tr[tr[x].rc].lazytr[x].lazy;72 }73 tr[x].lazy-1;74 }75 76 void change(int x,int l,int r,int y)77 {78 if(tr[x].lltr[x].rr)79 {80 tr[x].lazyy;81 return;82 }83 upd(x);84 int mid(tr[x].ltr[x].r)1;85 if(rmid) change(tr[x].lc,l,r,y);86 else if(lmid) change(tr[x].rc,l,r,y);87 else88 {89 change(tr[x].lc,l,mid,y);90 change(tr[x].rc,mid1,r,y);91 }92 upd(tr[x].lc);upd(tr[x].rc);93 tr[x].cltr[tr[x].lc].cl;94 tr[x].crtr[tr[x].rc].cr;95 tr[x].sumtr[tr[x].lc].sumtr[tr[x].rc].sum;96 if(tr[tr[x].lc].crtr[tr[x].rc].cl) tr[x].sum--;97 }98 99 void ffind(int x,int y,int z)
100 {
101 int f1top[x],f2top[y];
102 while(f1!f2)
103 {
104 if(dep[f1]dep[f2])
105 {
106 swap(f1,f2);
107 swap(x,y);
108 }
109 change(1,w[f1],w[x],z);
110 xfa[f1];
111 f1top[x];
112 }
113 if(dep[x]dep[y]) swap(x,y);
114 change(1,w[y],w[x],z);
115 }
116
117 int q1,q2,a1,a2;
118 int queryt(int x,int l,int r)
119 {
120 upd(x);
121 if(tr[x].lltr[x].rr)
122 {
123 if(q1tr[x].l) a1tr[x].cl;
124 if(q2tr[x].r) a2tr[x].cr;
125 return tr[x].sum;
126 }
127 int mid(tr[x].ltr[x].r)1;
128 if(rmid) return queryt(tr[x].lc,l,r);
129 if(lmid) return queryt(tr[x].rc,l,r);
130 int ansqueryt(tr[x].lc,l,mid)queryt(tr[x].rc,mid1,r);
131 if(tr[tr[x].lc].crtr[tr[x].rc].cl) ans--;
132 return ans;
133 }
134
135 int query(int x,int y)
136 {
137 int cl-1,cr-1,f1top[x],f2top[y];
138 int ans0;
139 while(f1!f2)
140 {
141 if(dep[f1]dep[f2])
142 {
143 q1w[f1];q2w[x];
144 ansqueryt(1,w[f1],w[x]);
145 if(a2cl) ans--;
146 cla1;
147 xfa[f1];f1top[x];
148 }
149 else
150 {
151 q1w[f2];q2w[y];
152 ansqueryt(1,w[f2],w[y]);
153 if(a2cr) ans--;
154 cra1;
155 yfa[f2];f2top[y];
156 }
157 }
158 if(dep[x]dep[y])
159 {
160 q1w[x];q2w[y];
161 ansqueryt(1,w[x],w[y]);
162 if(cla1) ans--;
163 if(cra2) ans--;
164 }
165 else
166 {
167 q1w[y];q2w[x];
168 ansqueryt(1,w[y],w[x]);
169 if(cra1) ans--;
170 if(cla2) ans--;
171 }
172 return ans;
173 }
174
175 int main()
176 {
177 int n,m;
178 scanf(%d%d,n,m);
179 for(int i1;in;i) scanf(%d,c[i]);
180 memset(first,0,sizeof(first));
181 for(int i1;in;i)
182 {
183 int x,y;
184 scanf(%d%d,x,y);
185 ins(x,y);ins(y,x);
186 }
187 dfs1(1,0);
188 dfs2(1,1);
189 build(1,n);
190 for(int i1;in;i) change(1,w[i],w[i],c[i]);
191 char s[10];
192 while(m--)
193 {
194 scanf(%s,s);
195 if(s[0]Q)
196 {
197 int x,y;
198 scanf(%d%d,x,y);
199 printf(%d\n,query(x,y));
200 }
201 else
202 {
203 int x,y,z;
204 scanf(%d%d%d,x,y,z);
205 ffind(x,y,z);
206 }
207 }
208 return 0;
209 } [BZOJ2243] 2016-05-12 16:34:01 转载于:https://www.cnblogs.com/Konjakmoyu/p/5486202.html
