CF1060E 题解()-其他

CF1060E 题解()

前言

题目传送门！

更好的阅读体验？

提供一种更加麻烦的换根 DP 写法。

思路

代码

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
struct Edge {int now, nxt;} e[N << 1];
int head[N], cur;
void add(int u, int v)
{
	e[++cur].now = v, e[cur].nxt = head[u];
	head[u] = cur;
}
ll sum[N], siz[N][2];
void dfs(int u, int fa)
{
	siz[u][0] = 1;
	for (int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].now;
		if (v == fa) continue;
		dfs(v, u);
		siz[u][0] += siz[v][1], siz[u][1] += siz[v][0];
		sum[u] += (sum[v] + siz[v][0]);
	}
}
ll ans[N];
void DFS(int u, int fa, int dep)
{
	for (int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].now;
		if (v == fa) continue;
		ans[v] = ans[u] + siz[1][dep & 1] - (siz[v][0] + siz[v][1]);
		DFS(v, u, dep + 1);
	}
}
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i < n; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v), add(v, u);
	}
	dfs(1, 0), ans[1] = sum[1], DFS(1, 0, 0);
	ll zlt = 0;
	for (int i = 1; i <= n; i++) zlt += ans[i];
	cout << zlt / 2;
	return 0;
}

希望能帮助到大家！

前言

题目传送门！

更好的阅读体验？

提供一种更加麻烦的换根 DP 写法。

思路

代码

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
struct Edge {int now, nxt;} e[N << 1];
int head[N], cur;
void add(int u, int v)
{
	e[++cur].now = v, e[cur].nxt = head[u];
	head[u] = cur;
}
ll sum[N], siz[N][2];
void dfs(int u, int fa)
{
	siz[u][0] = 1;
	for (int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].now;
		if (v == fa) continue;
		dfs(v, u);
		siz[u][0] += siz[v][1], siz[u][1] += siz[v][0];
		sum[u] += (sum[v] + siz[v][0]);
	}
}
ll ans[N];
void DFS(int u, int fa, int dep)
{
	for (int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].now;
		if (v == fa) continue;
		ans[v] = ans[u] + siz[1][dep & 1] - (siz[v][0] + siz[v][1]);
		DFS(v, u, dep + 1);
	}
}
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i < n; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v), add(v, u);
	}
	dfs(1, 0), ans[1] = sum[1], DFS(1, 0, 0);
	ll zlt = 0;
	for (int i = 1; i <= n; i++) zlt += ans[i];
	cout << zlt / 2;
	return 0;
}

希望能帮助到大家！