【每日一题】Treepath(树形dp)

Solution
记得寒假牛客有道题就是这道题的扩展，好像是求路径数目+博弈论。

表示以 i 为根的子树到 i 的距离为偶数/奇数的数目。
那么在dfs过程中，以 u 为根且子结点为 v 对答案的贡献是:

(子结点与父节点距离相差1，所以应操作不同奇偶性)
当然遍历完也需要把 v 的路径数合并到 u里面去:

Code

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("YES") ;}void put2(){ puts("NO") ;}void put3(){ puts("-1"); }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a =
(a*a)%p;b >>= 1;}return ans%p;}
const int mo=998244353; const int mod=1000000007;

const int manx=1e5+5;

vector<ll>g[manx];
ll ans;  ll dp[manx][2];

void dfs(ll u,ll pre){
    dp[u][0]=1;
    for(auto v: g[u]){
        if(v==pre) continue;
        dfs(v,u);
        ans+=dp[v][0]*dp[u][1];
        ans+=dp[v][1]*dp[u][0];
        dp[u][0]+=dp[v][1];
        dp[u][1]+=dp[v][0];
    }
}

int main(){
    ll n=read();
    for(int i=1;i<n;i++){
        ll u=read(),v=read();
        g[u].pb(v); g[v].pb(u);
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}