IT评测·应用市场-qidao123.com技术社区

标题: watch [打印本页]

---

作者: 欢乐狗    时间: 2024-9-13 14:36
标题: watch
平常很少做dfs序相干的题，算是复习一下吧。
题目大意

给你一棵树，每个节点有好坏两种颜色，初始都是白色，现在支持以下两种操作：

• 将一个节点的颜色翻转
  
• 询问某个节点与所有黑色节点分别求lca后得到的深度最大的结果
  

                                    n                         ,                         q                         ≤                         8                         ×                         1                                   0                            5                                       n,q≤8 \times 10^5                  n,q≤8×105。
题解

有一个著名但是赛时被我忘了的结论，某个点与一个特定点集合的lca中深度最大的必定是跟这个点dfs序最接近的两个点（前驱和后继）中的一个。
那么就变成蠢题了，对于翻转操作维护一下点集合，询问操作每次只需要找到dfs序的前驱后继并求lca再比力即可。对于维护和查找官方题解用的是线段树，而我选择set。
Code

1. #include<bits/stdc++.h>
2. using namespace std;
4. const int N=8e5+5;
6. int n,m,cnt,num,a[N],fa[N],dep[N],siz[N],dfn[N],tid[N],top[N],son[N],head[N];
7. bool b[N];
8. set<int> s;
10. struct edge{
11.         int to,nxt;
12. }e[N];
14. void add(int u,int v){
15.         e[++cnt]=(edge){v,head[u]};
16.         head[u]=cnt;
17. }
19. void dfs1(int u,int f,int d){
20.         siz[u]=1,fa[u]=f,dep[u]=d;
21.         for(int i=head[u];i;i=e[i].nxt){
22.                 int v=e[i].to;
23.                 dfs1(v,u,d+1);
24.                 siz[u]+=siz[v];
25.                 if(siz[v]>siz[son[u]]) son[u]=v;
26.         }
27. }
29. void dfs2(int u,int tp){
30.         dfn[u]=++num,tid[num]=u,top[u]=tp;
31.         if(!son[u]) return;
32.         dfs2(son[u],tp);
33.         for(int i=head[u];i;i=e[i].nxt){
34.                 int v=e[i].to;
35.                 if(v==son[u]) continue;
36.                 dfs2(v,v);
37.         }
38. }
40. int lca(int x,int y){
41.         while(top[x]!=top[y]){
42.                 if(dep[top[x]]<dep[top[y]]) swap(x,y);
43.                 x=fa[top[x]];
44.         }
45.         return dep[x]<dep[y]?x:y;
46. }
48. int main(){
49.         freopen("watch.in","r",stdin);
50.         freopen("watch.out","w",stdout);
51.         scanf("%d%d",&n,&m);
52.         for(int i=2,x;i<=n;i++){
53.                 scanf("%d",&x);
54.                 add(x,i);
55.         }
56.         dfs1(1,0,0);
57.         dfs2(1,1);
58.         for(int i=1,x;i<=m;i++){
59.                 scanf("%d",&x);
60.                 if(x>0){
61.                         b[x]=!b[x];
62.                         if(b[x]) s.insert(dfn[x]);
63.                         else s.erase(dfn[x]);
64.                 }
65.                 else{
66.                         x=-x;
67.                         if(s.size()==0){
68.                                 printf("0\n");
69.                                 continue;
70.                         }
71.                         set<int>::iterator it=s.lower_bound(dfn[x]);
72.                         int ans1=0,ans2=0;
73.                         if(it!=s.end()) ans1=lca(tid[*it],x);
74.                         if(it!=s.begin()){
75.                                 it--;
76.                                 ans2=lca(tid[*it],x);
77.                         }
78.                         if(!ans1&&!ans2) printf("0\n");
79.                         else if(!ans1||!ans2) printf("%d\n",ans1+ans2);
80.                         else printf("%d\n",dep[ans1]>dep[ans2]?ans1:ans2);
81.                 }
82.         }
83.         return 0;
84. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4