题目链接
题意简述
某公司中有 (n) 名员工。为方便起见，将这些员工从 1 至 (n) 编号。起初，员工之间相互独立。接下来，会有以下 (m) 次操作：
-
员工 (y) 成为员工 (x) 的上司。保证此前 (x) 没有上司。
-
员工 (x) 拿到一份文件并签字，随后交给他的上司。他的上司签字后，再交给更上一级。依此类推，直到文件传递到的那个人没有上司为止。
-
询问员工 (x) 是否在第 (i) 件文件上签过字。文件编号为上一件文件的编号再加 1，第一件文件的编号为 1。如果是，输出
YES，否则输出NO。
解法说明
显然，我们可以将员工之间的关系看作森林，将每个员工看作一个节点，其与上司的关系看作一条边。之所以不是一棵树，是因为在 (m) 次操作中，有些人可能并没有被指定上司，所以员工之间的关系很可能并不是一棵树而是森林。
通过观察题面可以发现，一个员工在成为另一个员工的上司后，就不会再有更改了。由于在线操作过于麻烦，我们可以考虑离线。
具体离线方法如下：
-
对于操作 1，直接连边即可，不过这里还要在线维护一个并查集；
-
对于操作 2，分别记下第一个和最后一个对文件签字的员工，后者就是前者所在的连通块的根，利用并查集查找；
-
对于操作 3，分别记下员工编号及文件编号，离线回答。
接下来分析如何回答询问。可以发现，如果询问的员工 (x) 在 最开始看到文件 (i) 的员工与最后看到文件 (i) 的员工之间的链上，那么 (x) 就看过文件。所以，问题就被转化为了判断 (x) 是否在这条链上。
考虑如何判断。
设 (st) 为链的起始点，(ed) 为截止点，可推得如 (x) 在链上，则 (text{lca}(x,st) = x) 且 (text{lca}(x,ed) = ed)，维护一个 LCA 即可求解。我这里用的是树剖求 LCA，倍增也可以。
还有一些细节需要注意。由于员工之间的关系是森林而非一棵树，所以我们在预处理树剖时应枚举每个点，如果该点是其所属的连通块的根，就对其进行一次预处理，且回答询问时应首先判断 (x) 与 (st)、(ed) 是否在同一连通块内，如果不在直接输出 NO，否则再执行下一步操作。
剩余细节详见下面代码中的注释。
通过代码
#include<bits/stdc++.h> using namespace std; #define int long long #define PII pair<int,int> #define mp make_pair const int N=1e5+10; namespace IO{ //快读 inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-'){ f=-1; } ch=getchar(); } while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } //快写 inline void write(int x){ if(x<0){ putchar('-'); x=-x; } if(x>9){ write(x/10); } putchar(x%10+'0'); } } using namespace IO; namespace code{ //链式前向星存图 int head[N],tot; struct node{ int ver,next; }t[N<<1]; void add(int x,int y){ t[++tot].ver=y,t[tot].next=head[x],head[x]=tot; } //并查集 int fa[N]; int getfa(int x){ if(fa[x]==x){ return x; } return fa[x]=getfa(fa[x]); } //树链剖分 int fat[N],size[N],son[N],deep[N],top[N]; void dfs1(int x){ size[x]=1; int maxson=-1; for(int i=head[x];i;i=t[i].next){ int y=t[i].ver; if(y==fat[x]){ continue; } fat[y]=x; deep[y]=deep[x]+1; dfs1(y); if(size[y]>maxson){ maxson=size[y]; son[x]=y; } size[x]+=size[y]; } } void dfs2(int x,int from){ top[x]=from; if(!son[x]){ return; } dfs2(son[x],from); for(int i=head[x];i;i=t[i].next){ int y=t[i].ver; if(y==son[x]||y==fat[x]){ continue; } dfs2(y,y); } } //求LCA int lca(int x,int y){ while(top[x]!=top[y]){ if(deep[top[x]]<deep[top[y]]){ swap(x,y); } x=fat[top[x]]; } if(deep[x]<deep[y]){ return x; } return y; } //主程序 int n,m,f_tot,q_tot; PII file[N],query[N]; void solve(){ n=read(),m=read(); for(int i=1;i<=n;i++){//并查集预处理 fa[i]=i; } for(int i=1;i<=m;i++){//离线处理 int op=read(); if(op==1){ int x=read(),y=read(); add(y,x);//单向边 fa[x]=getfa(y);//在线维护并查集 }else if(op==2){ int x=read(); file[++f_tot]=mp(x,getfa(x)); }else{ int x=read(),y=read(); query[++q_tot]=mp(x,y); } } for(int i=1;i<=n;i++){//枚举所有点 if(getfa(i)==i){//判断是否为所在连通块的根 deep[i]=1;//树剖预处理 fat[i]=i; dfs1(i); dfs2(i,i); } } for(int i=1;i<=q_tot;i++){ int x=query[i].first,y=query[i].second,st=file[y].first,ed=file[y].second; if(getfa(x)!=getfa(st)){//是否在同一个连通块 printf("NOn"); continue; } if(lca(x,st)==x&&lca(x,ed)==ed){//判断 printf("YESn"); }else{ printf("NOn"); } } } } using namespace code; signed main(){ solve(); return 0; } 
