论坛 › 物联网 › watch

欢乐狗 发表于 7 天前

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

#include<bits/stdc++.h>
using namespace std;

const int N=8e5+5;

int n,m,cnt,num,a,fa,dep,siz,dfn,tid,top,son,head;
bool b;
set<int> s;

struct edge{
        int to,nxt;
}e;

void add(int u,int v){
        e[++cnt]=(edge){v,head};
        head=cnt;
}

void dfs1(int u,int f,int d){
        siz=1,fa=f,dep=d;
        for(int i=head;i;i=e.nxt){
                int v=e.to;
                dfs1(v,u,d+1);
                siz+=siz;
                if(siz>siz]) son=v;
        }
}

void dfs2(int u,int tp){
        dfn=++num,tid=u,top=tp;
        if(!son) return;
        dfs2(son,tp);
        for(int i=head;i;i=e.nxt){
                int v=e.to;
                if(v==son) continue;
                dfs2(v,v);
        }
}

int lca(int x,int y){
        while(top!=top){
                if(dep]<dep]) swap(x,y);
                x=fa];
        }
        return dep<dep?x:y;
}

int main(){
        freopen("watch.in","r",stdin);
        freopen("watch.out","w",stdout);
        scanf("%d%d",&n,&m);
        for(int i=2,x;i<=n;i++){
                scanf("%d",&x);
                add(x,i);
        }
        dfs1(1,0,0);
        dfs2(1,1);
        for(int i=1,x;i<=m;i++){
                scanf("%d",&x);
                if(x>0){
                        b=!b;
                        if(b) s.insert(dfn);
                        else s.erase(dfn);
                }
                else{
                        x=-x;
                        if(s.size()==0){
                                printf("0\n");
                                continue;
                        }
                        set<int>::iterator it=s.lower_bound(dfn);
                        int ans1=0,ans2=0;
                        if(it!=s.end()) ans1=lca(tid[*it],x);
                        if(it!=s.begin()){
                                it--;
                                ans2=lca(tid[*it],x);
                        }
                        if(!ans1&&!ans2) printf("0\n");
                        else if(!ans1||!ans2) printf("%d\n",ans1+ans2);
                        else printf("%d\n",dep>dep?ans1:ans2);
                }
        }
        return 0;
}

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

查看完整版本: watch