哈理工第8回学校チーム試合C樹上経路カウント

タイトル:
Description
n個の頂点を持つツリーを指定するには、ツリー上のすべての長さが奇数のパスの数を統計する必要があります.パスの長さは、エッジを通るバーの数です.sからtとtからsは同じとみなされる.
Input
第1挙動試験データ群数T(1<=T<=5)である.各テストデータのセット:最初の行には頂点数を表す整数n(1<=n<=1 e 5)があり、次にn-1行に2つの整数u,vがあり、u,vの間にエッジが存在することを示す.
Output
パスの長さが奇数の整数です.
Sample Input
2
2
1 2
4
1 2
2 3
1 4
Sample Output
1
4
考え方:
この問題の典型的な木形dp問題は,1ノードをrootとし,dp【i】【0】はiをルートノードとするサブツリーの奇数サブノード個数を表し,dp【i】【1】はiをルートノードとするサブツリーの偶数サブノード個数を表し,dp【1】【0】+dp【1】【0】✖️dp【1】【1】が答え
コード:

#include 
#include 
#include 
#define ll long long
using namespace std;

int n;
vector zcy[100005];
int dp[100005][2];

void dfs(int inx, int father) {
    for (int i = 0; i < zcy[inx].size(); i++) {
        int ii = zcy[inx][i];
        if(ii ==father) continue;
        dfs(ii, inx);
        dp[inx][0] += dp[ii][1] + 1;
        dp[inx][1] += dp[ii][0];
    }
}

int main() {
    int T, a, b;
    scanf("%d", &T);
    while(T--) {
        memset(dp, 0, sizeof(dp));
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            zcy[i].clear();
        }
        for (int i = 0; i < n - 1; i++) {
            scanf("%d%d", &a, &b);
            zcy[a].push_back(b);
            zcy[b].push_back(a);
        }
        dfs(1, 0);
        ll ans = (ll)dp[1][0] * (dp[1][1] + 1);
        printf("%lld
", ans);
    }
    return 0;
}

転載は出典を明記してください!!!
間違って書かれていたり、全面的に書かれていないところがあれば、ホームページの連絡先で指摘してください.ありがとうございます.