题解 P4216 【[SCOI2015]情报传递】

YoungNeal

2018-06-11 21:14:11

Solution

题解在博客[食用](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; } ```