题目
思路
对于每个人，其权值为(m)结束时其的危险程度，换句话说：如果其没有侦察，其权值为(0)，如果其在(i)时刻开始侦察，那么其危险程度即为(m-i)。
而对于查询，我们不妨也改造一下其的(c)，如果一个人在(i)时刻大于(c)，那么其在(m)时刻结束时应该大于(c+m-i)，然后进行同样的改造就行了，就变成了求权值大于等于(c+m-i+1)的点的数量。
然后，我们把(x,y)拆成两部分，设(ty)为(lca(x,y))在(y)方向的儿子，那么就拆成：(x-lca(x,y))，(y-ty)两条路径。
不难发现，我们只要还能处理一个点到根节点的大于路径信息即可。
那么对于路径(x-y(y是x的祖先))而言，设(f_{x,c})为根节点到(x)的路径大于等于(c)的点的数量，那么这条路径就等于(f_{x,c}-f_{fa_y,c})，而一个点到根节点的路径信息可以用树状数组遍历一遍树离线处理出来，把每个询问需要用到的(f)存到需要点的(vector)中即可。
#include<cstdio>
#include<cstring>
#include<vector>
#define N 210000
using namespace std;
int n,m;
class QMQ
{
public:
int a[N];
inline int lowbit(int x){return x&-x;}
inline void change(int x,int k)
{
while(x<=m)a[x]+=k,x+=lowbit(x);
}
inline int getsum(int x)
{
int y=0;
while(x)y+=a[x],x-=lowbit(x);
return y;
}
}qmq;
inline void change(int x,int k){qmq.change(x+1,k);}
inline int findans(int l,int r){return qmq.getsum(r+1)-qmq.getsum(l);}
vector<pair<int,int> > f1[N]/*+*/,f2[N]/*-*/;
struct node
{
int y,next;
}a[N];int len,last[N];
inline void ins(int x,int y){len++;a[len].y=y;a[len].next=last[x];last[x]=len;}
int fa[N][20],dep[N];//17
void dfs1(int x)
{
for(int i=1;i<=17;i++)
{
fa[x][i]=fa[fa[x][i-1]][i-1];
if(!fa[x][i])break;
}
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
fa[y][0]=x;dep[y]=dep[x]+1;
dfs1(y);
}
}
inline int lca(int &x,int &y,int &tx,int &ty)//tx其实是没用的，tx就是lca
{
if(x==y){tx=x;ty=0;return x;}
if(dep[x]>dep[y])x^=y^=x^=y;
tx=x;ty=y;
for(int i=17;i>=0;i--)
{
if(dep[fa[ty][i]]>dep[tx])ty=fa[ty][i];
}
if(fa[ty][0]==tx)return tx;
if(dep[tx]<dep[ty])ty=fa[ty][0];
for(int i=17;i>=0;i--)
{
if(fa[tx][i]!=fa[ty][i])tx=fa[tx][i],ty=fa[ty][i];
}
return tx=fa[tx][0];
}
int ans[N],val[N];
void dfs2(int x)
{
for(vector<pair<int,int> >::iterator it=f2[x].begin();it!=f2[x].end();++it)
{
pair<int,int> y=*it;
if(y.second<m)ans[y.first]-=findans(y.second,m-1);
}
change(val[x],1);
for(vector<pair<int,int> >::iterator it=f1[x].begin();it!=f1[x].end();++it)
{
pair<int,int> y=*it;
if(y.second<m)ans[y.first]+=findans(y.second,m-1);
}
for(int k=last[x];k;k=a[k].next)dfs2(a[k].y);
change(val[x],-1);
}
int fuans[N],rt;
int main()
{
// freopen("std.in","r",stdin);
// freopen("vio.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;scanf("%d",&x);
if(x)ins(x,i);
else rt=i;
}
dfs1(rt);
scanf("%d",&m);
int q_len=0;
for(int i=1;i<=m;i++)
{
int type;scanf("%d",&type);
if(type==1)
{
int x,y,c,tx,ty;scanf("%d%d%d",&x,&y,&c);
c+=m-i;c++;
int z=lca(x,y,tx,ty);
q_len++;fuans[q_len]=dep[x]+dep[y]-2*dep[z]+1;
f1[x].push_back(make_pair(q_len,c));f2[tx].push_back(make_pair(q_len,c));
if(ty)f1[y].push_back(make_pair(q_len,c)),f2[ty].push_back(make_pair(q_len,c));
}
else
{
int x;scanf("%d",&x);
if(!val[x])val[x]=m-i;
}
}
dfs2(rt);
for(int i=1;i<=q_len;i++)printf("%d %d
",fuans[i],ans[i]);
return 0;
}