Point in atcoder-ABC-202 - E - Count Descendants subtree with distance root D

Title Link

General idea of the topic

find u i u_i The distance root (i.e. point 1) in the subtree of ui is d i d_i Number of di points

thinking

first, n , q ≤ 2 ∗ 1 0 5 n,q\leq2*10^5 n. Q ≤ 2 * 105 we can't do it directly by violence, otherwise T L E TLE TLE will chase you for 5 blocks, so I thought: we can easily find the number of points with equal distance to point 1 in the process of traversing the tree.

Then we can at every point x x x open an array to store points x x The number of numbers with equal distance to point 1 in the subtree of x, i.e t r e e i , j tree_{i,j} treei,j means i i In the subtree of i, the distance to point 1 is j j The number of points of j. But ah, T L E TLE Next to TLE M L E MLE MLE is very interested in my code without saying a word. Let's simplify our thinking.

We can enter all the d i d_i di, so we can use m a p map map type t r e e i tree_i treei only records distance d i d_i Number of di points. But if each d i d_i di is different from each other, so M L E MLE MLE can find us happily again.

To avoid M L E MLE MLE, let's go deeper. Now that we have entered them first, we can use some prefixes and ideas.

When we first visited this point, we put the requirements of this point d i d_i di number of distant points from t r e e 1 , d i tree_{1,d_i} One copy in tree1,di, i.e t r e e u i , d i = t r e e 1 , d i tree_{u_i,d_i}=tree_{1,d_i} treeui, di =tree1,di, at this time t r e e u i , d i tree_{u_i,d_i} treeui, di does not include u i u_i Point to point 1 distance of ui subtree d i d_i Number of di points.

After the son of this point visits, our t r e e 1 , d i tree_{1,d_i} tree1,di, the distance from point to point 1 in this subtree is d i d_i The number of di points is added.

Because we saved it t r e e u i , d i tree_{u_i,d_i} treeui, di is the distance from point to point 1 excluding this subtree d i d_i The number of di points, so we make t r e e u i , d i = t r e e 1 , d i − t r e e u i , d i tree_{u_i,d_i}=tree_{1,d_i}-tree_{u_i,d_i} Treeui, di =tree1,di − treeui, Di, that is, the distance from point to point 1 including this subtree is d i d_i The number of points of di minus the distance from point to point 1 excluding this subtree is d i d_i The number of di points, you can get the real t r e e u i , d i tree_{u_i,d_i} treeui​,di​​.

Then it can be output. Ahaaha, my task is completed.

CODE

#include<bits/stdc++.h>
using namespace std;

#define ll long long

const int maxn=1e6*2+5;

int n,m;
int dis[maxn],ns[maxn],nq[maxn],u[maxn],d[maxn];

bool vis[maxn],cis[maxn];

map<int,int>tree[maxn];
map<int,int>v[maxn];

vector<int>son[maxn];
vector<int>qt[maxn];

void dfs(int x)
{
    int i;
    // cout<<x<<endl;
    cis[x]=1;
    for(i=0;i<nq[x];i++)
    {
        if(dis[x]<=qt[x][i])
        {
            tree[x][qt[x][i]]=tree[1][qt[x][i]];
        }
    }
    if(vis[dis[x]]==1) tree[1][dis[x]]++;
    for(i=0;i<ns[x];i++)
    {
        if(!cis[son[x][i]])
        {
            dis[son[x][i]]=dis[x]+1;
            dfs(son[x][i]);
        }
    }
    if(x!=1)
    {
        for(i=0;i<nq[x];i++)
        {
            if(dis[x]<=qt[x][i])
            {
                tree[x][qt[x][i]]=tree[1][qt[x][i]]-tree[x][qt[x][i]];
            }
        }
    }
    return ;
}

int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        son[x].push_back(i);
        ns[x]++;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u[i],&d[i]);
        if(!v[u[i]][d[i]])
        {
            v[u[i]][d[i]]=1;
            qt[u[i]].push_back(d[i]);
            nq[u[i]]++;
            vis[d[i]]=1;
        }
    }
    dfs(1);
    for(int i=1;i<=m;i++)
    {
        printf("%d\n",tree[u[i]][d[i]]);
    }
}