NC20570. [SCOI2015]情报传递
描述
输入描述
第1行包含1个正整数n，表示情报员个数。笫2行包含n个非负整数，其中第i个整数Pi表示i号情报员上线的编号。特别地，若Pi=0，表示i号情报员是大头目。第3行包含1个正整数q，表示奈特公司将派发q个任务（每天一个）。随后q行，依次描述q个任务。每行首先有1个正整数k。若k=1，表示任务是传递情报，随后有3个正整数Xi、Yi、Ci，依次表示传递情报的起点、终点和风险控制值；若k=2，表示任务是搜集情报，随后有1个正整数Ti，表示搜集情报的情报员编号。
输出描述
对于每个传递情报任务输出一行，应包含两个整数，分别是参与传递情报的情报员个数和对该条情报构成威胁的情报员个数。
输出的行数应等于传递情报任务的个数，每行仅包含两个整数，用一个空格隔开。输出不应包含多余的空行和空格。
示例1
输入:
7 0 1 1 2 2 3 3 6 1 4 7 0 2 1 2 4 2 7 1 4 7 1 1 4 7 3
输出:
5 0 5 2 5 1
说明:
对于3个传递情报任务，都是经过 5名情报员，分别是4号、2号、1号、3号和 7号。
第1个任务，所有情报员 (危险值为 0) 都不对情报构成威胁；第2个任务，有2名情报员对情报构成威胁，分别是1号情报员 (危险值为 3) 和 4号情报员 (危险值为2)，7号情报员 (危险值为1) 并不构成威胁；第 3个任务，只有1名情报员对情报构成威胁。C++14(g++5.4) 解法, 执行用时: 359ms, 内存消耗: 40584K, 提交时间: 2020-09-28 23:57:23
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int N=2e5+10;
int son[N],siz[N],head[N],tot,cnt,id[N],dep[N],top[N],T[N],n,rt,Cnt,fa[N];
struct edge{
int next,to;
}e[N<<1];
struct Tree{
int l,r,sum;
}tree[N*50];
int build(int l,int r){
int id=++tot;tree[id].sum=0;
if(l==r)return id;
int mid=l+r>>1;
tree[id].l=build(l,mid);
tree[id].r=build(mid+1,r);
return id;
}
int update(int l,int r,int x,int rt){
int id=++tot;tree[id]=tree[rt];
if(l==r){tree[id].sum++;return id;}
int mid=l+r>>1;
if(x<=mid)tree[id].l=update(l,mid,x,tree[rt].l);
else tree[id].r=update(mid+1,r,x,tree[rt].r);
tree[id].sum=tree[tree[id].l].sum+tree[tree[id].r].sum;
return id;
}
int query(int l,int r,int L,int R,int rt){
if(L<=l&&r<=R)return tree[rt].sum;
int mid=l+r>>1,ans=0;
if(L<=mid)ans+=query(l,mid,L,R,tree[rt].l);
if(mid<R)ans+=query(mid+1,r,L,R,tree[rt].r);
return ans;
}
void add(int u,int v){
e[++cnt].next=head[u];
e[cnt].to=v;
head[u]=cnt;
}
void dfs(int u,int depth){
siz[u]=1;dep[u]=depth;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;dfs(v,depth+1);
siz[u]+=siz[v];if(siz[son[u]]<siz[v])son[u]=v;
}
}
void dfs1(int u,int tp){
top[u]=tp;id[u]=++Cnt;
if(son[u])dfs1(son[u],tp);
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;if(v==son[u])continue;dfs1(v,v);
}
}
pii get_sum(int u,int v,int p){
int tp1=top[u],tp2=top[v];
int ans=0,res=0;
while(tp1!=tp2){
if(dep[tp1]<dep[tp2])swap(tp1,tp2),swap(u,v);
ans+=query(1,n,id[tp1],id[u],p);res+=id[u]-id[tp1]+1;
u=fa[tp1];tp1=top[u];
}
if(dep[u]>dep[v])swap(u,v);
ans+=query(1,n,id[u],id[v],p);res+=id[v]-id[u]+1;
return {res,ans};
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int a;scanf("%d",&a);
if(a==0)rt=i;
else add(a,i),fa[i]=a;
}
dfs(rt,1);dfs1(rt,rt);
T[0]=build(1,n);
int q;scanf("%d",&q);
for(int i=1;i<=q;i++){
T[i]=T[i-1];
int op;scanf("%d",&op);
if(op==1){
int x,y,c;scanf("%d %d %d",&x,&y,&c);
int pre=max(0,i-c-1);
pii ans=get_sum(x,y,T[pre]);
printf("%d %d\n",ans.first,ans.second);
}else {
int x;scanf("%d",&x);
T[i]=update(1,n,id[x],T[i]);
}
}
}
C++11(clang++ 3.9) 解法, 执行用时: 203ms, 内存消耗: 18392K, 提交时间: 2020-04-01 13:26:03
#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
const int N=202333;
int dep[N],sz[N],size,tot,son[N],top[N],fa[N],begi[N],ed[N],head[N],ans[N][2],c,n,m,x,cnt,t[N];
struct zs{
int a,b,c,pos,opt;
}a[N];
struct node{
int next,to;
}e[N<<1];
inline void ins(int u,int v) {
e[++tot].to=v; e[tot].next=head[u]; head[u]=tot;
}
inline void dfs1(int x,int pre) {
dep[x]=dep[fa[x]=pre]+1; sz[x]=1;
for(int k=head[x];k;k=e[k].next) {
if(e[k].to==pre) continue;
dfs1(e[k].to,x);
sz[x]+=sz[e[k].to];
if(sz[e[k].to]>sz[son[x]]) son[x]=e[k].to;
}
}
void dfs2(int x,int tr) {
top[x]=tr;
if(son[x]) dfs2(son[x],tr);
for(int k=head[x];k;k=e[k].next) {
if(e[k].to==fa[x] || e[k].to==son[x]) continue;
dfs2(e[k].to,e[k].to);
}
}
inline int lca(int x,int y) {
int a,b;
a=top[x]; b=top[y];
while(a!=b) {
if(dep[a]<dep[b]) swap(a,b),swap(x,y);
x=fa[a]; a=top[x];
}
if(dep[x]<dep[y]) return x;else return y;
}
void dfs(int x){
begi[x]=++cnt;
for(int k=head[x];k;k=e[k].next) dfs(e[k].to);
ed[x]=cnt;
}
bool cmp(zs a,zs b){
return a.c==b.c?a.opt<b.opt:a.c<b.c;
}
inline void add(int x,int k){
while(x<=n) t[x]+=k,x+=x&-x;
}
inline int ask(int x){
int sum=0;
while(x) sum+=t[x],x-=x&-x;
return sum;
}
inline int read(){
int x=0,c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
return x;
}
int main(){
scanf("%d",&n);
rep(i,1,n) {x=read(); if(x)ins(x,i);}
dfs(1);
dfs1(1,0);
dfs2(1,1);
scanf("%d",&m);
rep(i,1,m){
a[i].opt=read();
if(a[i].opt==1){
a[i].a=read(); a[i].b=read(); a[i].c=read();
a[i].pos=++size;
a[i].c=i-a[i].c;
}else a[i].a=read(),a[i].c=i;
}
sort(a+1,a+1+m,cmp);
rep(i,1,m)if(a[i].opt==2){
add(begi[a[i].a],1); add(ed[a[i].a]+1,-1);
}else {
c=lca(a[i].a,a[i].b);
ans[a[i].pos][0]=dep[a[i].a]+dep[a[i].b]-2*dep[c]+1;
ans[a[i].pos][1]=ask(begi[a[i].a])+ask(begi[a[i].b])-ask(begi[c])-ask(begi[fa[c]]);
}
rep(i,1,size) printf("%d %d\n",ans[i][0],ans[i][1]);
}