「cousins」CF208 E.Blood Cousins（树上启发式合并）

cousins

题目链接：CF208E

Polycarpus got hold of a family relationship tree. The tree describes family relationships of n people, numbered 1 through n. Each person in the tree has no more than one parent.

Let’s call person a a 1-ancestor of person b, if a is the parent of b.

Let’s call person a a k-ancestor (k > 1) of person b, if person b has a 1-ancestor, and a is a (k - 1)-ancestor of b’s 1-ancestor.

Family relationships don’t form cycles in the found tree. In other words, there is no person who is his own ancestor, directly or indirectly (that is, who is an x-ancestor for himself, for some x, x > 0).

Let’s call two people x and y (x ≠ y) p-th cousins (p > 0), if there is person z, who is a p-ancestor of x and a p-ancestor of y.

Polycarpus wonders how many counsins and what kinds of them everybody has. He took a piece of paper and wrote m pairs of integers vi, pi. Help him to calculate the number of pi-th cousins that person vi has, for each pair vi, pi.

Input

The first input line contains a single integer n (1 ≤ n ≤ 105) — the number of people in the tree. The next line contains n space-separated integers r1, r2, …, rn, where ri (1 ≤ ri ≤ n) is the number of person i’s parent or 0, if person i has no parent. It is guaranteed that family relationships don’t form cycles.

The third line contains a single number m (1 ≤ m ≤ 105) — the number of family relationship queries Polycarus has. Next m lines contain pairs of space-separated integers. The i-th line contains numbers vi, pi (1 ≤ vi, pi ≤ n).

Output

print m space-separated integers — the answers to Polycarpus’ queries. Print the answers to the queries in the order, in which the queries occur in the input.

examples

inputCopy

0 1 1 0 4 4

1 1

1 2

2 1

2 2

4 1

5 1

6 1

outputCopy

0 0 1 0 0 1 1

题意：给你一棵树，输入x，k。x代表节点，k代表深度，这里的深度是以x为基准，从下往上的深度

现在设y为x在k深度下的祖先，现在问你和x同层的节点，有多少个祖先是y。

思路：感觉这是个超级有毒的题目，英语本来就不怎么好，翻译过来，我以为题目是问有没有超过k个堂兄弟，结果交上去还过了7组，拼命想bug，然而题目都看错了，怎么改也会是错的，于是百度题意，得到正确的题意后，发现这个题目需要转换，变成祖先的第k深度下有多少个孩子。所有我们需要去找节点的祖先，第一个想的方法肯定是定义一个fa数组保存每个节点祖先，然后对每个查询，递推查祖先就可以了，但是这个会超时，因为可能这棵树可能会是一条深度为1e5的链，所以需要优化，开一个vector fa[max]数组，在dfs时，把节点的每个祖先都存起来，这样也不行，爆内存。。。。，最后，熟悉dfs的过程可以发现，根本不需要二维数组，用一维数组就可以了。

代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define Max 1000005
#define mem(a,b) memset(a,b,sizeof(a));
#define pb push_back
#define mp make_pair
#define input iOS::sync_with_stdio(false);cin.tie(0);
#define debug printf("debug!!!\n");
const LL mod=1e9+7;
const ULL base=131;
const LL LL_MAX=9223372036854775807;
using namespace std;
struct node {
    int to,next;
} edge[Max];
struct ans {
    int to,next;
    int ans,fa;
} query[Max];

int head[Max],tot;
int qhead[Max],num;
int Son;
int cnt[Max],son[Max],dep[Max],Size[Max];
int ind[Max];
vector<int> fat[Max];
void init() {
    tot=0;
    num=0;
    mem(head,-1);
    mem(qhead,-1);
}
void addedge(int u,int v) {
    edge[tot].to=v;
    edge[tot].next=head[u];
    head[u]=tot++;
}
void addquery(int  u,int cot) {
    query[num].to=cot;
    query[num].next=qhead[u];
    qhead[u]=num++;
}

void getsd(int u,int fa,int d) {
    dep[u]=d,Size[u]=1;
    ind[dep[u]]=u;
    for(int t=qhead[u];t!=-1;t=query[t].next){
        int to=query[t].to;
        if(dep[u]-to<=0)
            query[t].fa=0;
        else
            query[t].fa=ind[dep[u]-to];
    }
    for(int t=head[u]; t!=-1; t=edge[t].next) {
        int to=edge[t].to;
        if(to!=fa){
            getsd(to,u,d+1);
            Size[u]+=Size[to];
            if(Size[to]>Size[son[u]])
                son[u]=to;
        }
    }
}
void add(int u,int fa,int val) {
    cnt[dep[u]]+=val;
    for(int t=head[u]; t!=-1; t=edge[t].next) {
        int to=edge[t].to;
        if(to!=fa && to!=Son) {
            add(to,u,val);
        }
    }
}
void dfs(int u,int fa,int keep) {
    for(int t=head[u]; t!=-1; t=edge[t].next) {
        int to=edge[t].to;
        if(to!=fa && to!=son[u])
            dfs(to,u,0);
    }
    if(son[u])
        dfs(son[u],u,1),Son=son[u];
    add(u,fa,1);
    Son=0;
    for(int t=qhead[u]; t!=-1; t=query[t].next) {
        int to=query[t].to;
        if(u==0) {
            query[t].ans=0;
        } else {
            query[t].ans+=cnt[dep[u]+to];
        }
    }
    if(!keep)
        add(u,fa,-1);
}
int main()
{
    init();
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        int fa;
        scanf("%d",&fa);
        addedge(fa,i);
        addedge(i,fa);
    }
    int m;
    scanf("%d",&m);
    while(m--) {
        int u,k;
        scanf("%d%d",&u,&k);
        addquery(u,k);
    }
    getsd(0,-1,0);
    int len=num;
    num=0;
    mem(qhead,-1);
    for(int i=0;i<len;i++)
        addquery(query[i].fa,query[i].to);
    dfs(0,-1,1);
    for(int i=0; i<num; i++)
        printf("%d ",query[i].ans==0?0:(query[i].ans-1));
    printf("\n");
    return 0;
}

CF208 E.Blood Cousins（树上启发式合并）

cousins

相关阅读

栏目导航

推荐阅读

热门阅读