首页 > 其他分享 >P9847 [ICPC2021 Nanjing R] Crystalfly

P9847 [ICPC2021 Nanjing R] Crystalfly

时间:2023-11-14 14:44:51浏览次数:35  
标签:ICPC2021 emplace P9847 int res maxx back Crystalfly 节点

P9847 [ICPC2021 Nanjing R] Crystalfly

你说得对,但是刻晴更可爱捏

翻译

给定一个 \(n(1\le n\le10^5)\) 个节点的树,每个节点上有 \(a_i\) 只晶蝶。派蒙最初在 \(1\) 号节点,并获得 \(1\) 号节点的所有晶蝶,接下来每一秒她可以移动到相邻的节点上并获得节点上的所有晶蝶,但是当她每到达一个节点 \(u\) 后,对于每个与 \(u\) 相邻的节点 \(v\),节点 \(v\) 上的的晶蝶会在 \(t_v(1\le t_v\le3)\) 秒内消失,在 \(t_v\) 秒后再到达节点 \(v\) 将无法获得节点上的晶蝶。现在需要你求出最多可以获得的晶蝶数。

分析

观察到特殊数据 \(t_i\le3\),不难想到只有两种情况:

  • 走进节点 \(u\) 的一棵子树后放弃其他子树,转化成和原问题相同的子问题。
  • 若 \(t_i=3\) 则可以进入一个节点后再退出并进入另一棵子树,转化成子问题。

因此考虑树上 DP。

定义 \(f_{u,0/1}\) 为遍历以 \(u\) 为根的整棵子树且 \(u\) 点的子节点的晶蝶是否消失的情况下所能获得的最大晶蝶数量。记与 \(u\) 相邻的非父亲节点中 \(t_i=3\) 的节点晶蝶数量的最大值和次大值(若存在,不存在特判即可)分别为 \(max1,max2\)。

如果当前节点不存在 \(t_i=3\) 的节点,那么 \(f_{u,0}=\sum\limits_{v\in son_u}f_{v,1},f_{u,1}=(\sum\limits_{v\in son_u}f_{v,1})+\max(a_v)\)。

如果当前节点存在 \(t_i=3\) 的节点,那么通过画图观察不难发现,记所有子节点的 \(f_{v,1}\) 的和 \(\sum\limits_{v\in son_u}f_{v,1}\) 为 \(sum\),\(f_{u,0}\) 结果不变,\(f_{u,1}=\max(f_{v,0}+a_v+sum-f_{v,1}+max1,f_{v,0}+a_v+sum-f_{v,1}+max2)\)。

这样最后的结果就变成了 \(f_{1,1}+a_1\)。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 1e5 + 5;
int f[maxn][2], a[maxn], TestCase, t[maxn], n;
vector<int> G[maxn], g[maxn];

inline void dfs(int u, int fa) {
	int maxx, res;
	maxx = res = 0;
	f[u][0] = f[u][1] = 0;
	
	for (auto v : G[u]) {
		if (v == fa) continue;
		dfs(v, u);
		res += f[v][1];
		maxx = max(maxx, a[v]);
	}
	f[u][0] = res, f[u][1] = res + maxx;
	if (g[u].size()) {
		int maxx1, maxx2, maxid1, maxid2;
		maxx1 = maxx2 = -2e18;
		maxid1 = maxid2 = 0;
		for (auto v : g[u]) {
			if (v == fa) continue;
			if (maxx1 < a[v]) {
				maxx2 = maxx1;
				maxid2 = maxid1;
				maxx1 = a[v];
				maxid1 = v;
			}
			else if (maxx2 < a[v]) {
				maxx2 = a[v];
				maxid2 = v;
			}
		}
		maxx = -2e18;
		for (auto v : G[u]) {
			if (v == fa) continue;
			if (v == maxid1) {
				if (maxid2 == 0) maxx = max(maxx, a[v] + f[v][0] + res - f[v][1]);
				else maxx = max(maxx, a[v] + f[v][0] + res - f[v][1] + maxx2);
			}
			else maxx = max(maxx, a[v] + f[v][0] + res - f[v][1] + maxx1);
		}
		f[u][1] = max(maxx, f[u][1]);
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> TestCase;
	while (TestCase--) {
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];
		for (int i = 1; i <= n; i++) cin >> t[i];
		for (int i = 1; i <= n; i++) G[i].clear(), g[i].clear();
		for (int i = 1; i < n; i++) {
			int u, v;
			cin >> u >> v;
			G[u].emplace_back(v), G[v].emplace_back(u);
			if (t[v] == 3) g[u].emplace_back(v);
            if (t[u] == 3) g[v].emplace_back(u);
		}
		dfs(1, 1);
		cout << a[1] + f[1][1] << "\n";
	}
	return 0;
}

Feedback

不知道是不是造数据的时候数据生成的问题,在判断相邻两边是否是 \(t=3\) 的点时:

if (t[v] == 3) g[u].emplace_back(v);
if (t[u] == 3) g[v].emplace_back(u);

if (t[v] == 3) g[u].emplace_back(v);

都可以通过本题。

显然后一种写法只有在 \(u\) 始终为 \(v\) 的根节点的时候才有正确性。

严重怀疑是不是 generator 采用了向前随机挂点的方法。

标签:ICPC2021,emplace,P9847,int,res,maxx,back,Crystalfly,节点
From: https://www.cnblogs.com/George-Pig-Orz/p/17831529.html

相关文章