CF 1060E. Sergey and Subway

flowchart 箭头图标 勿删

题目链接

题意：给你一棵树，然后连接两个有公共邻居的点，问你连完后，任意两点的距离之和。

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

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <math.h>

#include <bitset>

#include <vector>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#define MAXN 1010100

#define LL long long

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define ll __int64

#define INF 0x7fffffff

#define cs(s) freopen(s,"r",stdin)

#define mem(x) memset(x,0,sizeof(x))

#define PI acos(-1)

#define eps 1e-10

using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}

int lcm(int a,int 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;}

//head

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+=dp[i][1]*(n-dp[i][1]);

		res+=dp[i][2];

	}

	ans+=res*(n-res);

	cout<<ans/2;

	return 0;

}