solution
枚举起点和终点的LCA,然后将他们两两组合即可。
具体的,设f[i][0/1]表示以i为根的子树中,与根节点i的距离为偶数(0)奇数(1)的点的数量。
转移显然就是。
然后考虑统计答案,以为的两个节点,肯定不能在的同一个儿子里,所以转移的过程中,表示已经当前已经计算过得儿子造成的贡献,对于一个新的儿子,
code
/* * @Author: wxyww * @Date: 2020-04-14 11:33:18 * @Last Modified time: 2020-04-14 11:39:50 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 100010; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } struct node { int v,nxt; }e[N << 1]; int head[N],ejs; ll f[N][2]; void add(int u,int v) { e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs; } ll ans = 0; void dfs(int u,int fa) { f[u][0] = 1; for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(v == fa) continue; dfs(v,u); ans += f[v][1] * f[u][0]; ans += f[v][0] * f[u][1]; f[u][0] += f[v][1]; f[u][1] += f[v][0]; } } int main() { int n = read(); for(int i = 1;i < n;++i) { int u = read(),v = read(); add(u,v);add(v,u); } dfs(1,0); cout<<ans; return 0; }