生活在树上

ZHR 住在一有根棵树上（11 号节点为根），树上的每条边都有一个距离。由于他特别懒，所以他一天移动的距离不能超过 22，对于每个节点，问他在一天中可以通过这个节点到达多少个不同的节点。

这题是一个经典的换根dp问题，先求出每个点直接能到达的距离为1和距离为2的结点，距离大于2的结点就不用存了，因为肯定到不了，在以每一个结点为根，求出他不能直接到达的距离为2的结点，这个值为它的子节点距离为1的点，当然要减去1，是他们之间的一条边，已经被计算过了。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair<int, int> PII;
const int N = 1000010;
int q[N][3];
vector<PII> v[N];
int n;

int main()
{
    scanf("%d", &n);
    for(int i = 2; i <= n; i ++ )
    {
        int f, w;
        scanf("%d %d", &f, &w);
        if(w <= 2)
        {
            q[f][w] ++;
            q[i][w] ++;
            v[f].push_back({i, w});//存下距离为w的结点
            v[i].push_back({f, w});
        }
    }
    
    for(int i = 1; i <= n; i ++ )
    {
        for(auto &[f, w] : v[i])
            if(w == 1)
                q[i][2] += q[f][1] - 1;//换根dp
        printf("%d\n", q[i][1] + q[i][2] + 1);
    }
    
    return 0;
}