[BZOJ 3637]Query on a tree VI

偶然看见了这题,觉得自己 QTREE、COT 什么的都没有刷过的真是弱爆了……

一道思路很巧妙的题,终于是在约大爷的耐心教导下会了,真是太感谢约大爷了。

这题显然是树链剖分,但是链上维护的东西很恶心。其核心思想是找到一个相连的最浅同色节点,那么我只要维护每个点的子树中与他相连的点的数量即可

用 f[c][u] 表示在 u 的子树中与 u 相连 (假设 u 无色) 且颜色为 c 的点数

查询直接算出与 u 相连的最浅同色节点 a,ans=f[c[u]][a]

考虑修改,我们发现每次 u 被反转,影响到的点是 father[u] 一直往上,直到根或一个异色点(PS. 最浅异色 a 的 f[ ][a] 也会被改),而且他们的 f[][] 都是加一个数或减一个数

(PS2. father[u] 的 f[][] 会被改两次,因为 u 的颜色变了,导致 f[0][father[u]]、f[1][father[u]] 都在变)

区间修改,单点查询,于是用树状树组搞搞救过了

至于找到一个相连的最浅同色节点,可用线段树——比如:三叉神经树的做法

也可以在每条链上暴力挂 3 个 map 神马的……

反正是好 YY de 啦~

  1 #include <cstdio>
  2 #include <cstring>
  3 const int sizeOfPoint=100001;
  4 
  5 inline int getint();
  6 inline void putint(int);
  7 
  8 int n, m;
  9 int f[sizeOfPoint], d[sizeOfPoint], s[sizeOfPoint];
 10 int p[20][sizeOfPoint];
 11 int num, idx[sizeOfPoint], son[sizeOfPoint], top[sizeOfPoint];
 12 bool c[sizeOfPoint];
 13 
 14 struct node
 15 {
 16     int ll, rr;
 17     bool lc, rc;
 18     int len;
 19     node * l, * r;
 20     inline void maintain();
 21 };
 22 node * t;
 23 node memory_node[sizeOfPoint<<2], * port_node=memory_node;
 24 inline node * newnode(int, int);
 25 node * build(int, int);
 26 void update(node * , int);
 27 int query(node * , int, int);
 28 
 29 int sum[2][sizeOfPoint];
 30 inline int lowbit(int);
 31 inline void update(int * , int, int, int);
 32 inline int query(int * , int);
 33 
 34 struct edge {int point; edge * next;};
 35 edge memory_edge[sizeOfPoint<<1], * port_edge=memory_edge;
 36 edge * e[sizeOfPoint];
 37 inline edge * newedge(int, edge * );
 38 inline void link(int, int);
 39 inline int lg(int);
 40 void dfs_tree(int);
 41 void dfs_chain(int, int);
 42 inline int anc(int, int);
 43 inline void update(bool, int, int, int);
 44 inline int query(int);
 45 
 46 int main()
 47 {
 48     n=getint();
 49     for (int i=1;i<n;i++)
 50     {
 51         int u=getint(), v=getint();
 52         link(u, v);
 53     }
 54 
 55     memset(d, 0xFF, sizeof(d)); d[1]=0;
 56     dfs_tree(1);
 57     dfs_chain(1, 1);
 58     t=build(1, n);
 59     for (int i=1;i<=n;i++) update(sum[0], idx[i], idx[i], s[i]-1);
 60 
 61     m=getint();
 62     for (int i=1;i<=m;i++)
 63     {
 64         int o=getint(), u=getint();
 65 
 66         if (o==0)
 67         {
 68             int f=query(u);
 69             putint(1+query(sum[c[f]], idx[f]));
 70         }
 71         else if (u==1) c[u]^=1;
 72         else
 73         {
 74             int s=query(sum[c[u]], idx[u])+1;
 75             c[u]^=1;
 76             update(t, idx[u]);
 77 
 78             if (c[u]==c[f[u]])
 79             {
 80                 update(sum[!c[u]], idx[f[u]], idx[f[u]], -s);
 81                 int a=query(f[u]);
 82                 s=query(sum[c[u]], idx[u])+1;
 83                 if (a==1) update(c[u], f[u], a, s);
 84                 else update(c[u], f[u], f[a], s);
 85             }
 86             else
 87             {
 88                 int a=query(f[u]);
 89                 if (a==1) update(!c[u], f[u], a, -s);
 90                 else update(!c[u], f[u], f[a], -s);
 91                 s=query(sum[c[u]], idx[u])+1;
 92                 update(sum[c[u]], idx[f[u]], idx[f[u]], s);
 93             }
 94         }
 95     }
 96 
 97     return 0;
 98 }
 99 inline int getint()
100 {
101     register int num=0;
102     register char ch;
103     do ch=getchar(); while (ch<'0' || ch>'9');
104     do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9');
105     return num;
106 }
107 inline void putint(int num)
108 {
109     char stack[11];
110     register int top=0;
111     if (num==0) stack[top=1]='0';
112     for ( ;num;num/=10) stack[++top]=num%10+'0';
113     for ( ;top;top--) putchar(stack[top]);
114     putchar('
');
115 }
116 
117 inline void node::maintain()
118 {
119     lc=l->lc; rc=r->rc;
120     len=r->len;
121     if (len==r->rr-r->ll+1 && l->rc==r->lc) len+=l->len;
122 }
123 inline node * newnode(int ll, int rr)
124 {
125     node * ret=port_node++;
126     ret->ll=ll; ret->rr=rr;
127     ret->l=ret->r=NULL;
128     return ret;
129 }
130 node * build(int ll, int rr)
131 {
132     node * t=newnode(ll, rr);
133     if (ll==rr) t->lc=t->rc=c[ll], t->len=1;
134     else
135     {
136         int m=(ll+rr)>>1;
137         t->l=build(ll, m);
138         t->r=build(m+1, rr);
139         t->maintain();
140     }
141     return t;
142 }
143 void update(node * t, int k)
144 {
145     if (t->ll==t->rr) t->lc=t->rc=c[t->ll];
146     else
147     {
148         int m=(t->ll+t->rr)>>1;
149         if (k<=m) update(t->l, k);
150         else update(t->r, k);
151         t->maintain();
152     }
153 }
154 int query(node * t, int ql, int qr)
155 {
156     int ret=0;
157     if (t->ll==ql && t->rr==qr) ret=t->len;
158     else
159     {
160         int m=(t->ll+t->rr)>>1;
161         if (qr<=m) ret=query(t->l, ql, qr);
162         else if (ql>m) ret=query(t->r, ql, qr);
163         else
164         {
165             ret=query(t->r, m+1, qr);
166             if (ret==qr-m && t->r->lc==t->l->rc) ret+=query(t->l, ql, m);
167         }
168     }
169     return ret;
170 }
171 
172 inline int lowbit(int x)
173 {
174     return x & -x;
175 }
176 inline void update(int * c, int l, int r, int v)
177 {
178     for (   ;l<=n;l+=lowbit(l)) c[l]+=v;
179     for (r++;r<=n;r+=lowbit(r)) c[r]-=v;
180 }
181 inline int query(int * c, int i)
182 {
183     int ret=0;
184     for ( ;i;i-=lowbit(i)) ret+=c[i];
185     return ret;
186 }
187 
188 inline edge * newedge(int point, edge * next)
189 {
190     edge * ret=port_edge++;
191     ret->point=point; ret->next=next;
192     return ret;
193 }
194 inline void link(int u, int v)
195 {
196     e[u]=newedge(v, e[u]); e[v]=newedge(u, e[v]);
197 }
198 inline int lg(int u)
199 {
200     return !u?0:31-__builtin_clz(u);
201 }
202 void dfs_tree(int u)
203 {
204     s[u]=1;
205     for (int i=1;i<=lg(d[u]);i++) p[i][u]=p[i-1][p[i-1][u]];
206     for (edge * i=e[u];i;i=i->next) if (d[i->point]==-1)
207     {        
208         f[i->point]=u; d[i->point]=d[u]+1;
209         dfs_tree(i->point);
210         s[u]+=s[i->point];
211         if (s[i->point]>s[son[u]])
212             son[u]=i->point;
213     }
214 }
215 void dfs_chain(int u, int top_u)
216 {
217     idx[u]=++num; top[u]=u;
218     if (son[u]) dfs_chain(son[u], top_u);
219     for (edge * i=e[u];i;i=i->next) if (!idx[i->point])
220         dfs_chain(i->point, i->point);
221 }
222 inline int anc(int u, int k)
223 {
224     for (int i=19;i>=0;i--)
225         if ((k>>i)&1)
226             u=p[k][u];
227     return u;
228 }
229 inline void update(bool c, int u, int v, int s)
230 {
231     while (top[u]!=top[v])
232     {
233         update(sum[c], idx[top[u]], idx[u], s);
234         u=f[top[u]];
235     }
236     update(sum[c], idx[v], idx[u], s);
237 }
238 inline int query(int u)
239 {
240     for ( ; ; )
241     {
242         int l=query(t, idx[top[u]], idx[u]);
243 
244         if (l==d[top[u]]-d[u]+1)
245         {
246             if (top[u]==1) return 1;
247             if (c[top[u]]==c[f[top[u]]]) u=f[top[u]];
248             else return top[u];
249         }
250         else
251             return anc(u, l-1);
252     }
253 }
解锁新成就:rank last
原文地址:https://www.cnblogs.com/dyllalala/p/4154449.html