Treepath

Problem:

给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。
路径的起点与终点不能相同。

Solution:

解法一:

路径为偶数,也就是经过偶数跳边,由于是一棵树,所以统计从根出发经过偶数条边的点的个数和奇数条边的个数(也就是深度为奇数和偶数)
最后就是一个排列组合的问题了(奇数的选一条 + 奇数的再选一条)的种数 +(偶数选一条 + 偶数再选一条)的种数

解法二:

对于每一颗子树,统计以子树为根,每个点到根的距离奇数的有几个,偶数的有几个,然后在回溯时统计答案
答案 += 当前节点的奇数边条数 * 父节点偶数边条数 + 当前节点偶数边条数 * 父节点奇数边条数
(由于当前节点到父节点还有一条边,所以对于当前节点来说,其实它加上这条边后奇偶就互换了,所以可以理解为当前为根节点的子树中新加入的偶数边条数 * 之前存在的偶数边条数 + 当前为根节点的子树中新加入的奇数边条数 * 之前存在的奇数边条数)

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define _for(i,s,t) for(int i=s;i<t;i++)
#define _rof(i,s,t) for(int i=s;i>t;i--)
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define per(i,s,t) for(int i=s;i>=t;i--)
#define Ri(x) scanf("%d",&x)
#define Rii(x,y) scanf("%d%d",&x,&y)
#define INF 0x3f3f3f3f
using namespace std;
template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
typedef long long ll;
const int maxn = 1e5 + 10;
int n,odd,even;
ll ans;
vector<int> G[maxn << 1];
// ---------------------- 解法一 ---------------------------- 
void dfs(int nowp,int fa,int dep){
    (dep & 1)?(++even):(++odd);
    _for(i,0,G[nowp].size()){
        if(G[nowp][i] != fa){
            dfs(G[nowp][i],nowp,!dep);
        }
    }
}
void solve1(){
    dfs(1,0,0);
    cout<<((odd*1ll * (odd - 1)*1ll)>>1) + ((even*1ll * (even - 1)*1ll)>>1)<<endl;
}

// ------------------------------- 解法二 ----------------------------------
int dp[maxn][2];// 节点i的子树中奇偶边条数 0:偶,1:奇 
void dfs2(int nowp,int fa){
    dp[nowp][0] = 1;
    _for(i,0,G[nowp].size()){
        if(G[nowp][i] != fa){
            int to = G[nowp][i];
            dfs2(to,nowp);
            ans += dp[nowp][1] * dp[to][0] + dp[nowp][0] * dp[to][1];
            dp[nowp][0] += dp[to][1];
            dp[nowp][1] += dp[to][0];
        }
    }
} 
void solve2(){
    dfs2(1,0);
    cout<<ans<<endl;
}
int main(){
    IOS;
    int x,y;
    cin>>n;
    rep(i,2,n){
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    //solve1();
    solve2();
    return 0;
}

/**
Problem:
给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。
路径的起点与终点不能相同。

Solution: 
解法一: 
路径为偶数,也就是经过偶数跳边,由于是一棵树,所以统计从根出发经过偶数条边的点的个数和奇数条边的个数(也就是深度为奇数和偶数) 
最后就是一个排列组合的问题了(奇数的选一条 + 奇数的再选一条)的种数 +(偶数选一条 + 偶数再选一条)的种数  
解法二:
对于每一颗子树,统计以子树为根,每个点到根的距离奇数的有几个,偶数的有几个,然后在回溯时统计答案
答案 += 当前节点的奇数边条数 * 父节点偶数边条数 + 当前节点偶数边条数 * 父节点奇数边条数 
(由于当前节点到父节点还有一条边,所以对于当前节点来说,其实它加上这条边后奇偶就互换了,所以可以理解为当前为根节点的子树中新加入的偶数边条数 * 之前存在的偶数边条数 + 当前为根节点的子树中新加入的奇数边条数 * 之前存在的奇数边条数) 
*/