BZOJ 4771 七彩树

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4771

题意：

一棵 n 个点的有根树，编号依次为 1 到 n，其中 1 号点是根节点。每个节点都被染上了某一种颜色，其中第 i 个节点的颜色为 c[i]。如果 c[i]=c[j]，那么我们认为点 i 和点 j 拥有相同的颜色。定义 depth[i] 为 i 节点与根节点的距离，为了方便起见，你可以认为树上相邻的两个点之间的距离为 1。

询问 x 子树里且 depth 不超过 depth[x]+d 的所有点中出现了多少种本质不同的颜色。

这个子树内和距离不超过 d 的限制可以转移到二维平面上考虑，然后二维数据结构维护...？

显然维护不了，因为信息没法合并。

换一个套路，对层建主席树。

对于同色点对，在 lca 处丧失一个贡献，为了不重不漏只统计 dfs 序相邻的那些，这个对每组颜色开个 set 维护即可。

#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100010
#define ll long long
using namespace std;
char xB[1<<15],*xS=xB,*xT=xB;
#define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
namespace graph
{
    int head[N],cnt=1;
    struct zgz
    {
        int next,to;
    }edge[N];
    void add(int from,int to)
    {
        edge[cnt].to=to;
        edge[cnt].next=head[from];
        head[from]=cnt++;
    }
    void clear()
    {
        cnt=1;
        memset(head,0,sizeof(head));
    }
};
using namespace graph;
int T;
int n,m;
int c[N],anc[N][18];
int deep[N],tim[N],dfn,sz[N];
void dfs(int x)
{
    tim[x]=++dfn,sz[x]=1;
    for(int i=head[x];i;i=edge[i].next)
    {
        int to=edge[i].to;
        deep[to]=deep[x]+1;
        dfs(to);
        sz[x]+=sz[to];
    }
}
int p[N];
bool cmp(const int &a,const int &b)
{return deep[a]<deep[b];}
int root[N];
namespace seg
{
    int ch[N*100][2],sum[N*100],tot;
    void clear()
    {
        tot=0;
    }
    void update(int &x,int y,int l,int r,int pos,int v)
    {
        x=++tot,ch[x][0]=ch[y][0],ch[x][1]=ch[y][1],sum[x]=sum[y]+v;
        if(l==r)return ;
        int mid=(l+r)>>1;
        if(pos<=mid) update(ch[x][0],ch[y][0],l,mid,pos,v);
        else update(ch[x][1],ch[y][1],mid+1,r,pos,v);
    }
    int ask(int x,int l,int r,int L,int R)
    {
        if(!x)return 0;
        if(l>=L&&r<=R)return sum[x];
        int mid=(l+r)>>1,ret=0;
        if(L<=mid) ret+=ask(ch[x][0],l,mid,L,R);
        if(R>mid)  ret+=ask(ch[x][1],mid+1,r,L,R);
        return ret;
    }
}
int lca(int x,int y)
{
    if(deep[x]>deep[y])swap(x,y);
	for(int j=17;j>=0;j--)
	if(deep[x]<=deep[anc[y][j]])y=anc[y][j];
	if(x==y)return y;
	for(int j=17;j>=0;j--)
	if(anc[x][j]!=anc[y][j])x=anc[x][j],y=anc[y][j];
	return anc[y][0];
}
struct point
{
    int x,d;
};
bool operator < (const point &a,const point &b)
{return a.d<b.d;}
set<point> S[N];
set<point>::iterator it,It,IT;
int main()
{
    T=read();
    while(T--)
    {
        n=read(),m=read();
        clear();seg::clear();dfn=0;
        for(int i=1;i<=n;i++)S[i].clear();

        for(int i=1;i<=n;i++)c[i]=read(),p[i]=i;

        for(int i=2;i<=n;i++)
        anc[i][0]=read(),add(anc[i][0],i);

        deep[1]=1;
        dfs(1);
        for(int j=1;j<=17;j++)
        for(int i=1;i<=n;i++)anc[i][j]=anc[anc[i][j-1]][j-1];

        sort(p+1,p+n+1,cmp);

        int now=1;
        for(int i=1;i<=n;i++)
        {
            root[i]=root[i-1];
            while(deep[p[now]]==i&&now<=n)
            {
                int x=p[now];
                seg::update(root[i],root[i],1,n,tim[x],1);
                point k;
                k.x=x,k.d=tim[x];
                it=S[c[x]].insert(k).first;
                It=it,It++;
                int tmp=0;
                if(it!=S[c[x]].begin())
                {
                    IT=it,IT--;
                    seg::update(root[i],root[i],1,n,tim[lca(x,(*IT).x)],-1);
                    tmp++;
                }
                if(It!=S[c[x]].end())
                seg::update(root[i],root[i],1,n,tim[lca(x,(*It).x)],-1),tmp++;
                if(tmp==2)
                {
                    IT=it,IT--;
                    seg::update(root[i],root[i],1,n,tim[lca((*It).x,(*IT).x)],1);
                }
                now++;
            }
        }
        int lst=0;
        while(m--)
        {
            int x=read(),d=read();
            x^=lst,d^=lst;
            lst=seg::ask(root[min(deep[x]+d,deep[p[n]])],1,n,tim[x],tim[x]+sz[x]-1);
            printf("%d\n",lst);
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

#include <set>

#include <cmath>

#include <queue>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 100010

#define ll long long

using namespace std;

char xB[1<<15],*xS=xB,*xT=xB;

#define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

namespace graph

{

int head[N],cnt=1;

struct zgz

{

int next,to;

}edge[N];

void add(int from,int to)

{

edge[cnt].to=to;

edge[cnt].next=head[from];

head[from]=cnt++;

}

void clear()

{

cnt=1;

memset(head,0,sizeof(head));

}

};

using namespace graph;

int T;

int n,m;

int c[N],anc[N][18];

int deep[N],tim[N],dfn,sz[N];

void dfs(int x)

{

tim[x]=++dfn,sz[x]=1;

for(int i=head[x];i;i=edge[i].next)

{

int to=edge[i].to;

deep[to]=deep[x]+1;

dfs(to);

sz[x]+=sz[to];

}

int p[N];

bool cmp(const int &a,const int &b)

{return deep[a]<deep[b];}

int root[N];

namespace seg

{

int ch[N*100][2],sum[N*100],tot;

void clear()

{

tot=0;

}

void update(int &x,int y,int l,int r,int pos,int v)

{

x=++tot,ch[x][0]=ch[y][0],ch[x][1]=ch[y][1],sum[x]=sum[y]+v;

if(l==r)return ;

int mid=(l+r)>>1;

if(pos<=mid) update(ch[x][0],ch[y][0],l,mid,pos,v);

else update(ch[x][1],ch[y][1],mid+1,r,pos,v);

}

int ask(int x,int l,int r,int L,int R)

{

if(!x)return 0;

if(l>=L&&r<=R)return sum[x];

int mid=(l+r)>>1,ret=0;

if(L<=mid) ret+=ask(ch[x][0],l,mid,L,R);

if(R>mid) ret+=ask(ch[x][1],mid+1,r,L,R);

return ret;

}

int lca(int x,int y)

{

if(deep[x]>deep[y])swap(x,y);

for(int j=17;j>=0;j--)

if(deep[x]<=deep[anc[y][j]])y=anc[y][j];

if(x==y)return y;

for(int j=17;j>=0;j--)

if(anc[x][j]!=anc[y][j])x=anc[x][j],y=anc[y][j];

return anc[y][0];

}

struct point

{

int x,d;

};

bool operator < (const point &a,const point &b)

{return a.d<b.d;}

set<point> S[N];

set<point>::iterator it,It,IT;

int main()

{

T=read();

while(T--)

{

n=read(),m=read();

clear();seg::clear();dfn=0;

for(int i=1;i<=n;i++)S[i].clear();

for(int i=1;i<=n;i++)c[i]=read(),p[i]=i;

for(int i=2;i<=n;i++)

anc[i][0]=read(),add(anc[i][0],i);

deep[1]=1;

dfs(1);

for(int j=1;j<=17;j++)

for(int i=1;i<=n;i++)anc[i][j]=anc[anc[i][j-1]][j-1];

sort(p+1,p+n+1,cmp);

int now=1;

for(int i=1;i<=n;i++)

{

root[i]=root[i-1];

while(deep[p[now]]==i&&now<=n)

{

int x=p[now];

seg::update(root[i],root[i],1,n,tim[x],1);

point k;

k.x=x,k.d=tim[x];

it=S[c[x]].insert(k).first;

It=it,It++;

int tmp=0;

if(it!=S[c[x]].begin())

{

IT=it,IT--;

seg::update(root[i],root[i],1,n,tim[lca(x,(*IT).x)],-1);

tmp++;

}

if(It!=S[c[x]].end())

seg::update(root[i],root[i],1,n,tim[lca(x,(*It).x)],-1),tmp++;

if(tmp==2)

{

IT=it,IT--;

seg::update(root[i],root[i],1,n,tim[lca((*It).x,(*IT).x)],1);

}

now++;

}

int lst=0;

while(m--)

{

int x=read(),d=read();

x^=lst,d^=lst;

lst=seg::ask(root[min(deep[x]+d,deep[p[n]])],1,n,tim[x],tim[x]+sz[x]-1);

printf("%d\n",lst);

}

zgz233

zgz233

BZOJ 4771 七彩树

l1ll5

Comments | NOTHING