Dis2(dfs树）

Dis2

•  比赛主页
•  我的提交

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

给出一颗nn个点n−1n−1条边的树，点的编号为1,2,...,n−1,n1,2,...,n−1,n，对于每个点i(1≤i≤n)i(1≤i≤n)，输出与点ii距离为22的点的个数。 

两个点的距离定义为两个点最短路径上的边的条数。 

第一行一个正整数nn。

接下来n−1n−1行每行两个正整数ui,viui​,vi​表示点ui,viui​,vi​之间有一条边。

输入共nn行，第ii行输出一个整数表示与点ii距离为22的点的个数。

示例1

复制

4
1 2
2 3
3 4

复制

1
1
1
1

点1,31,3的距离为22，点2,42,4的距离为22。

1≤ui,vi≤n≤2000001≤ui​,vi​≤n≤200000

思路：

距离为2的点的个数=父亲节点的边树-1+子树边树-1

dfs遍历树就行

int n;
const int MAX=2e5+10;
vectorg[MAX];
int cnt[MAX];
void dfs(int u,int f){
    if(f>0) cnt[u]+=g[f].size()-1;
    for(int i=0;i>n;
    for(int i=1;i>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    
    for(int i=1;i<=n;i++){
        cout<