BZOJ4771: 七彩树-白红宇

BZOJ4771: 七彩树

阅读量：5037 次

发布时间：2019-06-12

本文共 2546 字，大约阅读时间需要 8 分钟。

题解: 对于每个节点他只会对这个节点到根这条路径上的点产生贡献所以我们考虑树链的并找到每个节点能作用的深度最低的位置然后对于深度建主席树,权值为dfs序的下标通过set来维护树链的并最后查询即可

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #define mp make_pair#define pb push_back#define pii pair
               
                #define link(x) for(edge *j=h[x];j;j=j->next)#define inc(i,l,r) for(int i=l;i<=r;i++)#define dec(i,r,l) for(int i=r;i>=l;i--)const int MAXN=1e5+10;const double eps=1e-8;#define ll long longusing namespace std;struct edge{int t;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;void add(int x,int y){o->t=y;o->next=h[x];h[x]=o++;}ll read(){ ll x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return x*f;}typedef struct node{ int l,r,sum;}node;node d[MAXN*81];int f[MAXN][21],dep[MAXN],p[MAXN],fp[MAXN],cnt,cnt1,rt[MAXN],a[MAXN],n,q,num[MAXN],id[MAXN];set
                
                 s[MAXN];set
                 
                  ::iterator ite,ip;void dfs(int x,int fa,int deep){ f[x][0]=fa;dep[x]=deep+1;p[x]=++cnt;fp[p[x]]=x;num[x]=1; link(x){ if(j->t!=fa)dfs(j->t,x,deep+1),num[x]+=num[j->t]; }}void dfs1(int x){ for(int i=1;i<=20;i++)f[x][i]=f[f[x][i-1]][i-1]; link(x)if(j->t!=f[x][0])dfs1(j->t);}int Lca(int u,int v){ if(dep[u]
                  
                   >1; if(t<=mid)update(d[x].l,d[y].l,l,mid,t,vul); else update(d[x].r,d[y].r,mid+1,r,t,vul);}int ans;void querty(int x,int y,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr){ans+=d[y].sum-d[x].sum;return ;} int mid=(l+r)>>1; if(ql<=mid)querty(d[x].l,d[y].l,l,mid,ql,qr); if(qr>mid)querty(d[x].r,d[y].r,mid+1,r,ql,qr);}bool cmp(int aa,int bb){return dep[aa]

4771: 七彩树

Time Limit: 5 Sec Memory Limit: 256 MB

Submit: 1520 Solved: 432

[][][]

Description

给定一棵n个点的有根树，编号依次为1到n，其中1号点是根节点。每个节点都被染上了某一种颜色，其中第i个节

点的颜色为c[i]。如果c[i]=c[j]，那么我们认为点i和点j拥有相同的颜色。定义depth[i]为i节点与根节点的距离

，为了方便起见，你可以认为树上相邻的两个点之间的距离为1。站在这棵色彩斑斓的树前面，你将面临m个问题。

每个问题包含两个整数x和d，表示询问x子树里且depth不超过depth[x]+d的所有点中出现了多少种本质不同的颜色

。请写一个程序，快速回答这些询问。

Input

第一行包含一个正整数T(1<=T<=500)，表示测试数据的组数。

每组数据中，第一行包含两个正整数n(1<=n<=100000)和m(1<=m<=100000)，表示节点数和询问数。

第二行包含n个正整数，其中第i个数为c[i](1<=c[i]<=n)，分别表示每个节点的颜色。

第三行包含n-1个正整数，其中第i个数为f[i+1](1<=f[i]<i)，表示节点i+1的父亲节点的编号。

接下来m行，每行两个整数x(1<=x<=n)和d(0<=d<n)，依次表示每个询问。

输入数据经过了加密，对于每个询问，如果你读入了x和d，那么真实的x和d分别是x xor last和d xor last，

其中last表示这组数据中上一次询问的答案，如果这是当前数据的第一组询问，那么last=0。

输入数据保证n和m的总和不超过500000。

Output

对于每个询问输出一行一个整数，即答案。

Sample Input

5 8

1 3 3 2 2

1 1 3 3

1 0

0 0

3 0

1 3

2 1

2 0

6 2

4 1

Sample Output

转载于:https://www.cnblogs.com/wang9897/p/9753641.html

你可能感兴趣的文章