树上距离之和 1060E

CodeForces - 1060E 

链接：https://vjudge.net/problem/1926461/origin

题意:2e5个结点的无向树，求对每条路径si,求Ans=

看了别人的博客,知道Ans=所有路径长度之和+奇长度路径的条数

奇妙的解法，对于这种要涉及到树中每一条路径的题目，我一直有一个天真的想法，就是把树中所有路径的长度都求出来

但是貌似所有的题目都不会有这种做法，由此，我觉得，应该是这样做复杂度非常高吧，所以大家都会避开这种做法

因此，对于这种题目，只能对每一条边出发，计算每一条边的贡献

路径长度值和=

奇长度路径数= 树中奇层节点数*树中偶层节点数

代码:

//Problem:
//Date:
//Skill:
//Bug:
/////////////////////////////////////////Definations/////////////////////////////////////////////////
//循环控制
#define CLR(a) memset((a),0,sizeof(a))
#define F(i,a,b) for(int i=a;i<=int(b);++i)
#define F2(i,a,b) for(int i=a;i>=int(b);--i)
#define RE(i,n)  for(int i=0;i<int(n);i++)
#define RE2(i,n) for(int i=1;i<=int(n);i++)
//输入输出
//#define INC(c) do{scanf("%c",&c);}while(isspace(c))
//#define ON cout<<endl
#define PII pair<int,int>
using namespace std;
const int inf = 0x3f3f3f3f;
const long long llinf = 0x3f3f3f3f3f3f3f3f;
////////////////////////////////////////Options//////////////////////////////////////////////////////
typedef long long ll;
#define stdcpph
#define CPP_IO

#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#ifdef CPP_IO
#include<iostream>
#include<iomanip>
#include<string>
#else
#include<stdio.h>
#endif
#endif
////////////////////////////////////////Basic Functions//////////////////////////////////////////////
template<typename INint>
inline void IN(INint &x)
{
	x = 0; int f = 1; char c; cin.get(c);
	while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
	while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
	x *= f;
}
template<typename INint>
inline void OUT(INint x)
{
	if (x > 9)OUT(x / 10);
	cout.put(x % 10 + '0');
}
////////////////////////////////////////Added Functions//////////////////////////////////////////////
const ll maxn = ll(2e5+4);
ll n;
ll ans(0);//总数，分前后
ll dp[2] = { 0 };
vector<ll>G[maxn];

ll cou(ll x, ll fl=0, ll f = -1)
{
	++dp[fl & 1];
	ll tot(1);
	RE(i, G[x].size())
	{
		ll to = G[x][i];
		if (to == f)continue;

		ll cnt = cou(to,fl+1, x);
		tot += cnt;
		ans += cnt * (n - cnt);
	}
	return tot;
}
////////////////////////////////////////////Code/////////////////////////////////////////////////////
int main()
{
	//freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
	ll T(1), times(0);
#ifdef CPP_IO// CPP_IO
	std::ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	//cin >> T;
#else
	//IN(T);
#endif 
/////////////////////////////////////////////////////////////////////////////////////////////////////
	while (++times, T--)
	{
		cin >> n;
		RE2(i, n - 1)
		{
			ll a, b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a);
		}
		cou(1);
		ans += dp[0] * dp[1];
		ans /= 2;
		cout << ans << endl;
	}
	/////////////////////////////////////////////////////////////////////////////////////////////////////
	return 0;
}