题解 P4216 【[SCOI2015]情报传递】
YoungNeal
2018-06-11 21:14:11
题解在博客[食用](https://www.cnblogs.com/YoungNeal/p/9169259.html)效果更佳哦~
## Solution
将收集情报看作染色操作,那么对于编号为 $idx$ 的询问,显然要求的是在 $idx-c-1$ 或更早这一条链上有多少点被染过色。
容易想到离线处理,按照 $idx-c-1$ 从小到大排序,并实时树上染色。
对于求两点距离,显然可以用两点深度之和再减去 $lca$ 的深度的二倍,求 $lca$ 可以在做第二问时顺便求出,所以我们返回一个 $pair$ 类型即可。
## Code
```cpp
#include<cstdio>
#include<cctype>
#include<algorithm>
#define N 200005
#define blank putchar(' ')
#define nxtline putchar('\n')
#define max(A,B) ((A)>(B)?(A):(B))
#define min(A,B) ((A)<(B)?(A):(B))
#define swap(A,B) ((A)^=(B)^=(A)^=(B))
int ques[N][5],q;
int n,m,cnt,pos,tot;
int sze[N],son[N],fa[N];
int sum[N<<2],ans[N],d[N];
int head[N],dfn[N],top[N];
struct Node{
int x,y,z;
int idx,ans1,ans2;
}node[N];
struct Edge{
int to,nxt;
}edge[N];
void add(int x,int y){
edge[++cnt].to=y;
edge[cnt].nxt=head[x];
head[x]=cnt;
}
bool cmp1(Node a,Node b){
return a.idx-a.z<b.idx-b.z;
}
bool cmp2(Node a,Node b){
return a.idx<b.idx;
}
int getint(){
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
void write(int x){
if(x>9) write(x/10);
putchar(x%10+'0');
}
void first_dfs(int now){
sze[now]=1;
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
d[to]=d[now]+1;
fa[to]=now;
first_dfs(to);
sze[now]+=sze[to];
if(sze[to]>sze[son[now]])
son[now]=to;
}
}
void second_dfs(int now,int low){
top[now]=low;
dfn[now]=++tot;
if(son[now])
second_dfs(son[now],low);
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
if(to==son[now])
continue;
second_dfs(to,to);
}
}
void pushup(int cur){
sum[cur]=sum[cur<<1]+sum[cur<<1|1];
}
void modify(int cur,int l,int r,int ql,int qr){
if(l==r){
sum[cur]=1;
return;
}
int mid=l+r>>1;
if(ql<=mid)
modify(cur<<1,l,mid,ql,qr);
else
modify(cur<<1|1,mid+1,r,ql,qr);
pushup(cur);
}
int query(int cur,int l,int r,int ql,int qr){
if(ql<=l and r<=qr)
return sum[cur];
int mid=l+r>>1,ans=0;
if(ql<=mid)
ans+=query(cur<<1,l,mid,ql,qr);
if(mid<qr)
ans+=query(cur<<1|1,mid+1,r,ql,qr);
return ans;
}
std::pair<int,int> ask(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]])
swap(x,y);
ans+=query(1,1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(d[x]<d[y])
swap(x,y);
ans+=query(1,1,n,dfn[y],dfn[x]);
return std::make_pair(y,ans);
}
signed main(){
n=getint();int root;
for(int i=1;i<=n;i++){
int p=0;
if((p=getint())==0)
root=i;
else
add(p,i);
}
first_dfs(root);second_dfs(root,root);
m=getint();
for(int i=1;i<=m;i++){
if(getint()==1){
node[++pos].x=getint();
node[pos].y=getint();
node[pos].z=getint();
node[pos].idx=i;
} else{
ques[++q][1]=getint();
ques[q][2]=i;
}
}
std::sort(node+1,node+1+pos,cmp1);
int now=0;
for(int i=1;i<=pos;i++){
while(now<q and node[i].idx-node[i].z>ques[now+1][2]){
now++;
modify(1,1,n,dfn[ques[now][1]],dfn[ques[now][1]]);
}
std::pair<int,int> p=ask(node[i].x,node[i].y);
node[i].ans1=d[node[i].x]+d[node[i].y]+1-2*d[p.first];
node[i].ans2=p.second;
}
std::sort(node+1,node+1+pos,cmp2);
for(int i=1;i<=pos;i++){
write(node[i].ans1);blank;
write(node[i].ans2);nxtline;
}
return 0;
}
```