bzoj 4448 [Scoi2015]情报传递(主席树,LCA)

时间:2022-03-13 20:57:36

【题目链接】

http://www.lydsy.com/JudgeOnline/problem.php?id=4448

【题意】

给定一颗树,询问一条路径上权值小于t-c的点数。

【思路】

将一个2查询的出现时间作为该点的权值,按照树的形态建主席树,然后将权值插入,线段树结点中记录该区间的所有点数。

对于一个1查询,即查询u,v路径上权值小于t-c的点数,t为查询的出现时间。在主席树上统计,设ans(x)表示T[x]中小于t-c的点数,答案为ans(u)+ans(v)-ans(lca(u,v))-ans(fa(lca(u,v)))。

【代码】

 #include<set>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define trav(u,i) for(int i=front[u];i;i=e[i].nxt)
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; typedef long long ll;
const int N = 2e5+; ll read() {
char c=getchar();
ll f=,x=;
while(!isdigit(c)) {
if(c=='-') f=-; c=getchar();
}
while(isdigit(c))
x=x*+c-'',c=getchar();
return x*f;
} struct Edge {
int v,nxt;
}e[N<<];
int en=,front[N];
void adde(int u,int v)
{
e[++en]=(Edge){v,front[u]}; front[u]=en;
} struct Tnode {
Tnode *ls,*rs;
int sum;
}*T[N],mempool[N*],*G=mempool; Tnode * Nw(Tnode*l,Tnode*r,int x) {
G->ls=l,G->rs=r,G->sum=x;
return G++;
}
Tnode* build(Tnode* p,int l,int r,int pos) {
int val=pos==? p->sum:p->sum+;
if(l==r)
return Nw(T[N-],T[N-],val);
else {
int mid=l+r>>;
if(pos<=mid) return Nw(build(p->ls,l,mid,pos),p->rs,val);
else return Nw(p->ls,build(p->rs,mid+,r,pos),val);
}
}
int query(Tnode* x,int l,int r,int pos)
{
if(l==r) { return x->sum; }
else {
int mid=l+r>>;
if(pos<=mid) return query(x->ls,l,mid,pos);
else return x->ls->sum+query(x->rs,mid+,r,pos);
}
} int n,m,tot,val[N],que[N][];
int top[N],son[N],siz[N],dep[N],fa[N]; void dfs1(int u,int father)
{
siz[u]=; son[u]=;
T[u]=build(T[father],,m,val[u]);
trav(u,i) if(e[i].v!=father) {
int v=e[i].v;
fa[v]=u;
dep[v]=dep[u]+;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int tp)
{
top[u]=tp;
if(son[u]) dfs2(son[u],tp);
trav(u,i) if(e[i].v!=fa[u]&&e[i].v!=son[u])
dfs2(e[i].v,e[i].v);
}
int lca(int u,int v)
{
while(top[u]!=top[v]) {
if(dep[top[u]]<dep[top[v]]) swap(u,v);
u=fa[top[u]];
}
return dep[u]<dep[v]? u:v;
} int main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
n=read();
int rt=,op,x,y,z;
FOR(i,,n) {
x=read();
if(!x) rt=i;
else adde(x,i);
}
m=read();
FOR(i,,m) {
op=read();
if(op==)
x=read(),val[x]=i;
else {
++tot;
que[tot][]=read(),que[tot][]=read(),que[tot][]=read();
que[tot][]=i;
}
}
dep[rt]=;
T[]=Nw(G,G,);
T[N-]=Nw(G,G,);
dfs1(rt,);
dfs2(rt,rt);
FOR(i,,tot) {
x=que[i][],y=que[i][],z=que[i][];
int LCA=lca(x,y),ans=dep[x]+dep[y]-dep[LCA]-dep[fa[LCA]];
if(que[i][]-z-<=) printf("%d 0\n",ans);
else {
int tmp=;
tmp+=query(T[x],,m,que[i][]-z-);
tmp+=query(T[y],,m,que[i][]-z-);
tmp-=query(T[LCA],,m,que[i][]-z-);
tmp-=query(T[fa[LCA]],,m,que[i][]-z-);
printf("%d %d\n",ans,tmp);
}
}
return ;
}