atcoder-ABC-202 - E - Count Descendants子树中距离根为D的点

题目链接

找到 u i u_i ui​的子树中距离根(即1号点)为 d i d_i di​的点的数量

首先， n , q ≤ 2 ∗ 1 0 5 n,qleq2*10^5 n,q≤2∗105我们不可以直接暴力去做，不然 T L E TLE TLE会追你5条街，所以我就想到了：我们在遍历树的过程中，可以很轻松的求出到点1距离相等的点的个数。

那我们就可以在每一个点 x x x开一个数组来存储点 x x x的子树内到点1距离相等的数的个数,即 t r e e i , j tree_{i,j} treei,j​表示 i i i的子树内，到点1距离为 j j j的点的个数。但是啊， T L E TLE TLE旁边的 M L E MLE MLE二话不说就对我的代码十分感兴趣，那我们在化简一下思路。

我们可以先输入所有的 d i d_i di​，这样的话我们就可以用 m a p map map类型的 t r e e i tree_i treei​只记录距离 d i d_i di​的点的个数。但如果每个 d i d_i di​互不相同，那 M L E MLE MLE又可以快乐的找到我们了。

为躲避 M L E MLE MLE，我们再深入一下。既然我们都先输入了，那我们可以利用一些前缀和思想。

我们第一访问这个点的时候，把这个点要求的 d i d_i di​远的点的个数从 t r e e 1 , d i tree_{1,d_i} tree1,di​​里拷贝一份，即 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​​，这个时候的 t r e e u i , d i tree_{u_i,d_i} treeui​,di​​是不包括 u i u_i ui​的子树的点到点1距离 d i d_i di​的点的个数。

等这一个点的儿子访问完以后，我们的 t r e e 1 , d i tree_{1,d_i} tree1,di​​就可以把这一棵子树里的点到点1距离是 d i d_i di​的点的个数加入。

因为我们之前存下来的 t r e e u i , d i tree_{u_i,d_i} treeui​,di​​是不包括这一棵子树的点到点1距离为 d i d_i di​的点的个数，所以我们使 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​​， 即包括这一棵子树的点到点1距离为 d i d_i di​的点的个数 减去 不包括这一棵子树的点到点1距离为 d i d_i di​的点的个数 ，就可以得到真正的 t r e e u i , d i tree_{u_i,d_i} treeui​,di​​。

然后就可以输出了，啊哈哈哈，我的任务完成了。

#include
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];

maptree[maxn];
mapv[maxn];

vectorson[maxn];
vectorqt[maxn];

void dfs(int x)
{
    int i;
    // cout<
        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
        if(!cis[son[x][i]])
        {
            dis[son[x][i]]=dis[x]+1;
            dfs(son[x][i]);
        }
    }
    if(x!=1)
    {
        for(i=0;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("%dn",tree[u[i]][d[i]]);
    }
}