题目:

考察点:

树上DFS、long long、思维

侃侃:

之前做过一道类似的题目,所以想到应该往哪个方向去想。

Code:

#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int maxn = 1e5 + 10;

vector<int>G[maxn];

int deep[maxn],n;

int u,v;

void DFS(int u,int fa) {
    for(int i = 0; i < G[u].size(); i ++) {
        int v = G[u][i];
        if(v != fa) {
            deep[v] = deep[u] + 1;
            DFS(v,u); 
        }
    }
    return ;
}

int main(void) {
    scanf("%d",&n);
    for(int i = 1; i < n; i ++) {
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    DFS(1,-1);
    LL ne = 0,pos = 0;
    LL res = 0;
    for(int i = 2; i <= n; i ++) {
        if(deep[i] & 1) ne ++;
        else {
            pos ++;
            res ++;
        }
    }
    res += (ne * (ne - 1)) / 2 + (pos * (pos - 1)) / 2;
    printf("%lld\n",res);
    return 0;
}

后记:

哈哈,虽然跟之前做过的一道题类似,不过自己写出来AC还是比较开心的,听说这道题是树形DP
的简单题,菜菜的我见到 DP 就 凉凉,先好好打好基础，加油！