CF 1060E. Sergey and Subway

题目链接
题意：给你一棵树，然后连接两个有公共邻居的点，问你连完后，任意两点的距离之和。
一开始看这种题，还不怎么会做，借鉴了这位大佬的博客，get到了新技能，当我们求树上任意俩点的距离之时，可以转化问题，不看点，而看边，每条边的使用次数是固定的，每条边使用的次数为：这条边左边的顶点数*右边的顶点数，而由于我们可以将相隔一个点的两个点连起来，所以，如果是偶数的距离，我们可以2个2个跳，就是距离的一半，奇数呢就是（距离+1）/2，而奇数的距离只能在偶数和奇数层产生，所以用 $dp\left[now\right]\left[2\right]$dp[now][2]记录当前节点 $now$now的层数， $dp\left[now\right]\left[1\right]$dp[now][1]表示由上一个节点pre出发，要经过 $now$now才能到的点数（包括自己），那么 $(n-dp[now\left]\right[1\left]\right)\ast dp\left[now\right]\left[1\right]$(n−dp[now][1])∗dp[now][1]就表示 $pre->now$pre−>now这条边的使用次数。

#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define LL long long
#define SZ(X) X.size()
#define pii pair<int,int>
#define ALL(X) X.begin(),X.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 2e5 + 11;
vector<int>v[N];
int n, dp[N][3];
void dfs(int now, int pre, int sta) {
	dp[now][1]++;
	dp[now][2] = sta;
	for (int k : v[now]) {
		if (k == pre)continue;
		dfs(k, now, sta ^ 1);
		dp[now][1] += dp[k][1];
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i < n; i++) {
		int s, t;
		cin >> s >> t;
		v[s].pb(t);
		v[t].pb(s);
	}
	dfs(1, 0, 0);
	LL ans, res;
	ans = res = 0;
	for (int i = 1; i <= n; i++) {
		ans += 1ll*dp[i][1] * (n - dp[i][1]);
		res += dp[i][2];
	}
	ans += 1ll*res * (n - res);
	cout << ans / 2;
	return 0;
}