P4216[SCOI2015情报传递 树上主席树

题意：维护一棵树，某些点有点权（没有则为正无穷），点权为正整数，查询树上路径点权小于等于某个值的点的个数。

分析:考虑维护主席树，root[i]数组存储第i个节点到根的点权的权值线段树的树根。更具体地，把第i个节点到根的路径上的点权累积到权值线段树中，对一个询问x,y，记lca为z,查询值为k，答案ans=que(root[x],root[fa[z]],1,m,k)+que(root[y],root[fa[z]],1,m,k)-que(root[z],root[fa[z]],1,m,k)

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+100;
inline int read()
{
    register char c=getchar();
    int x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+c-48;c=getchar();}
    return x*f;
}
struct edge{int y,n;}e[N<<1];
struct ques{int x,y,z,opt,id;}q[N<<1];
struct segtree{int lc,rc;int val;}s[N<<7];
int n,m,rot;
int st[N][23],dep[N];
int head[N],cnt;
int root[N],tot,dfn[N],tim,rk[N],mod,num=1;
int ans[N],siz[N];
void ad(int x,int y){e[++cnt].n=head[x];e[cnt].y=y;head[x]=cnt;}
void go(int u,int fa)
{
    dep[u]=dep[fa]+1;st[u][0]=fa;rk[u]=++tim;
    for(int i=1;i<=18;++i)st[u][i]=st[st[u][i-1]][i-1];
    for(int i=head[u];i;i=e[i].n)go(e[i].y,u);
}
bool cmp(ques c,ques d){return c.opt>d.opt;}
bool mcp(ques c,ques d){return rk[c.x]<rk[d.x];}
int lca(int x,int y)
{
    if(x==y)return x;
    if(dep[x]<dep[y])swap(x,y);
    for(int i=18;i>=0;--i)
        if(dep[st[x][i]]>=dep[y])
            x=st[x][i];
    if(x==y)return x;
    for(int i=18;i>=0;--i)
        if(st[x][i]!=st[y][i])
        x=st[x][i],y=st[y][i];
    return st[x][0];
}
void init()
{
    n=read();//1~n
    for(int i=1;i<=n;++i)
    {
        int x=read();
        if(x!=0)
        ad(x,i);
        else
        rot=i;
    }
    go(rot,0);
    m=read();
    for(int i=1;i<=m;++i)
    {
        q[i].opt=read();
        q[i].x=read();
        q[i].id=i;
        if(q[i].opt==1)
        {
            ++mod;
            q[i].y=read();
            q[i].z=read();
        }
    }

}
void build(int &i,int l,int r)
{
    if(!i)i=++tot;
    if(l==r)return ;int mid=(l+r)>>1;
    build(s[i].lc,l,mid);build(s[i].rc,mid+1,r);
}
void upd(int &i,int id,int l,int r,int x,int z)
{
    if(!i)i=++tot;
    s[i].val=s[id].val+z;
    if(l==r && l==x)return ;int mid=(l+r)>>1;
    if(x<=mid){s[i].rc=s[id].rc;upd(s[i].lc,s[id].lc,l,mid,x,z);}
    else {s[i].lc=s[id].lc;upd(s[i].rc,s[id].rc,mid+1,r,x,z);}
}
void rep(int u)//maybe wrong
{
    if(num<=m-mod && q[num].x==u)
    upd(root[u],root[st[u][0]],1,m,q[num++].id,1);
    else root[u]=root[st[u][0]];
    /*
        former wrong:
        while(q[num].x==u && num<=m-mod)
            upd(root[u],root[st[u][0]],1,m,q[num++].id,1);
    */
    for(int i=head[u];i;i=e[i].n)rep(e[i].y);
}
int que(int i,int id,int l,int r,int x)
{
    int mid=(l+r)>>1;
    if(r<=x)return s[i].val-s[id].val;
    if(x>mid)
        return que(s[i].rc,s[id].rc,mid+1,r,x)+s[s[i].lc].val-s[s[id].lc].val;
    return que(s[i].lc,s[id].lc,l,mid,x);
}
void work()
{
    build(root[0],1,m);
    sort(q+1,q+1+m,cmp);
    sort(q+1,q+1+m-mod,mcp);rep(rot);
    for(int i=1;i<=m;++i)ans[i]=-1;
    for(int i=m-mod+1;i<=m;++i)
    {
        int x=q[i].x,y=q[i].y,z=q[i].z;
        int zu=lca(x,y),pre=0,bak=0,pot=0;
        if(q[i].id-z-1>0)
        {
            pre=que(root[x],root[st[zu][0]],1,m,q[i].id-z-1);
            bak=que(root[y],root[st[zu][0]],1,m,q[i].id-z-1);
            pot=que(root[zu],root[st[zu][0]],1,m,q[i].id-z-1);
        }
        ans[q[i].id]=pre+bak-pot;
        siz[q[i].id]=dep[x]+dep[y]-2*dep[st[zu][0]]-1;
    }

    for(int i=1;i<=m;++i)
        if(ans[i]!=-1)printf("%d %d\n",siz[i],ans[i]);
}
int main()
{
    freopen("intelligence.in","r",stdin);
    freopen("intelligence.out","w",stdout);
    init();
    work();
    return 0;
}