[HDU5709]Claris Loves Painting(线段树合并,主席树)

发布于 2018-02-18  168 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU5709]Claris Loves Painting(线段树合并,主席树)

Description

Claris loves painting very much, so he painted a tree with beautiful colors.
The tree is a rooted tree with n nodes which are conveniently labeled by 1,2,...,n. Its root is the 1-st node, and the i-th node is painted with color ci. If ci=cj, then we think these two nodes have the same color.
We define depthi as the distance between the i-th node and the root, and simply, the distance between two adjacent nodes is always 1.
Standing in front of this beautiful tree, Claris comes up with m questions.
In each question, there are two integers x and d, which means that Claris wants to know the number of different kinds of colors occur in S, where S={v|v in x′s subtree and depthv≤depthx+d}.

Http

HDU

Tag

线段树合并,主席树

题目大意

一棵有根树,树上每一个点有可能相同的颜色,现在要求回答若干个询问,求在\(u\)的子树内与\(u\)相距不超过\(d\)的点有多少种颜色。强制在线。

解决思路

先不考虑颜色的限制,假设问题是询问在一个点的子树中与\(u\)相距不超过\(d\)的节点个数,那么这个可以用线段树来维护。具体来说,对于每一个点维护一棵线段树,线段树维护的区间\([l,r]\)表示深度在\([l,r]\)内的节点个数。这个可以直接从儿子线段树合并转移过来。
再考虑加上颜色的限制。由于一种颜色只算一次,不妨我们对于每一种颜色就只算深度最浅的那个,那么我们对于每一个点再维护一棵线段树,这个树中的第\(i\)号位置维护在这棵子树内颜色为\(i\)的最浅的点的深度,那么,合并的时候就取两者中更浅的那个点作为当前的值,然后由于这时颜色有了冲突,于是再修改第一棵线段树中的值,具体来说就是在第一棵线段树中把更深的那个减掉,因为如果我们依次合并的话一次只会有一个冲突。
直接这么做是会爆空间的,考虑到实际从下往上合并的时候,实际用到的空间并不多,并且还有很多重复,所以可以借助主席树的思想,动态开点并重复利用已知信息。
另外,由于题目中给出了一个点的父亲编号小于自己的编号,所以树\(dfs\)可以直接用\(for\)代替。
少用\(memset\)。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=100100;
const int inf=2147483647;

class SegmentData
{
public:
    int key,ls,rs;
};

int n,m,nodecnt;
int Fa[maxN],Col[maxN],Depth[maxN];//父节点,颜色,深度
SegmentData S[maxN*110];//线段树
int T1[maxN],T2[maxN];//分别对应两棵线段树的根

int Modify(int rt,int l,int r,int pos,int opt);//修改
int Merge1(int r1,int r2,int l,int r);//合并第一棵线段树
int Merge2(int r1,int r2,int l,int r,int u);//合并第二棵线段树
int Query(int now,int l,int r,int d);//查询深度小于d的颜种数

int main()
{
    int T;scanf("%d",&T);
    while (T--)
    {
        nodecnt=0;
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++) scanf("%d",&Col[i]);
        for (int i=2;i<=n;i++) scanf("%d",&Fa[i]);
        Depth[1]=1;for (int i=2;i<=n;i++) Depth[i]=Depth[Fa[i]]+1;//得到深度
        for (int i=1;i<=n;i++)//初始化每一棵线段树
        {
            T1[i]=Modify(0,1,n,Depth[i],1);//注意这里的0
            T2[i]=Modify(0,1,n,Col[i],Depth[i]);
        }
        for (int i=n;i>=2;i--)//把子树信息合并
        {
            T1[Fa[i]]=Merge1(T1[Fa[i]],T1[i],1,n);
            T2[Fa[i]]=Merge2(T2[Fa[i]],T2[i],1,n,Fa[i]);
        }
        int lastans=0;
        for (int i=1;i<=m;i++)
        {
            int u,dep;scanf("%d%d",&u,&dep);
            u^=lastans;dep^=lastans;
            printf("%d\n",lastans=Query(T1[u],1,n,min(Depth[u]+dep,n)));
        }
    }
    return 0;
}

int Modify(int rt,int l,int r,int pos,int opt)
{
    int nrt=++nodecnt;S[nrt].key=S[rt].key+opt;
    if (l==r) return nrt;
    int mid=(l+r)>>1;
    if (pos<=mid) S[nrt].ls=Modify(S[rt].ls,l,mid,pos,opt),S[nrt].rs=S[rt].rs;
    else S[nrt].ls=S[rt].ls,S[nrt].rs=Modify(S[rt].rs,mid+1,r,pos,opt);
    return nrt;
}

int Merge1(int r1,int r2,int l,int r)
{
    if ((r1==0)||(r2==0)) return r1+r2;
    int nrt=++nodecnt;S[nrt].key=S[r1].key+S[r2].key;
    if (l==r) return nrt;
    int mid=(l+r)>>1;
    S[nrt].ls=Merge1(S[r1].ls,S[r2].ls,l,mid);
    S[nrt].rs=Merge1(S[r1].rs,S[r2].rs,mid+1,r);
    return nrt;
}

int Merge2(int r1,int r2,int l,int r,int u)
{
    if ((r1==0)||(r2==0)) return r1+r2;
    int nrt=++nodecnt;
    if (l==r)
    {
        if (S[r1].key>S[r2].key){
            S[nrt].key=S[r2].key;T1[u]=Modify(T1[u],1,n,S[r1].key,-1);
        }
        else{
            S[nrt].key=S[r1].key;T1[u]=Modify(T1[u],1,n,S[r2].key,-1);
        }
        return nrt;
    }
    int mid=(l+r)>>1;
    S[nrt].ls=Merge2(S[r1].ls,S[r2].ls,l,mid,u);
    S[nrt].rs=Merge2(S[r1].rs,S[r2].rs,mid+1,r,u);
    return nrt;
}

int Query(int now,int l,int r,int d)
{
    if (now==0) return 0;
    if (r<=d) return S[now].key;
    int mid=(l+r)>>1;
    int ret=Query(S[now].ls,l,mid,d);
    if (d>=mid+1) ret+=Query(S[now].rs,mid+1,r,d);
    return ret;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU5709]Claris Loves Painting(线段树合并,主席树)


HNCJ OIer