牛客Treepath

Treepath

题目链接

题意:

给一棵树，让求两个点距离为偶数的点有多少对。

题解：

两个点的距离可以换为：d[x] + d[y] - 2 * d[lca];(d数组为到根节点的距离)
于是后面的-2*d[lca]不影响奇偶性。所以到根节点奇偶性相同的点可以组成一对。就很简单了。
代码:

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 1e5+5;
int a[maxn];
vector<int> vv[maxn];
typedef long long ll;
int dis[maxn];
void dfs(int x,int fa,int dep)
{
   
	dis[x] = dep;
	for (int i = 0; i < vv[x].size(); i ++ )
	{
   
		int v = vv[x][i];
		if(v == fa)
			continue;
		dfs(v,x,dep ^ 1);
	}
}

int main()
{
   
	int n;
	scanf("%d",&n);
	for(int i = 1; i < n; i ++ )
	{
   
		int x,y;
		scanf("%d%d",&x,&y);
		vv[x].push_back(y);
		vv[y].push_back(x);
	}
	dfs(1,0,0);
	int s1 = 0;
	int s2 = 0;
	for (int i = 1; i <= n; i ++ )
	{
   
		if(dis[i])
			s1 ++ ;
		else
			s2 ++;
	}
	printf("%lld\n",1ll * s1 * (s1 - 1) / 2 + 1ll * s2 * (s2 - 1) /2);
}