P10135 [USACO24JAN] Potion Farming S
每个叶子恰好走一次,若叶子个数为 $v$,则只需考虑前 $v$ 次遍历。若一个子树中有 $n$ 次药水出现,$m$ 个叶子,则其对答案的贡献为 $min(n, m)$
1N = int(1e5 + 19)2p = [0] * N3cnt = [0] * N4dep = [0] * N5tot = 06mx = 07f = [0] * N8fa = [0] * N9g = [[] for _ in range(N)]10depid = [[] for _ in range(N)]11
12def dfs(node, parent):13 global mx, tot14 dep[node] = dep[parent] + 115 fa[node] = parent40 collapsed lines
16 mx = max(dep[node], mx)17 depid[dep[node]].append(node)18 flag = False19 for neighbor in g[node]:20 if neighbor != parent:21 dfs(neighbor, node)22 flag = True23 if not flag:24 tot += 125 f[node] += 126
27def read():28 return int(input().strip())29
30def write(value, end_char):31 print(value, end=end_char)32
33n = read()34for i in range(1, n + 1):35 p[i] = read()36for _ in range(1, n):37 a, b = read(), read()38 g[a].append(b)39 g[b].append(a)40dfs(1, 1)41for i in range(1, tot + 1):42 cnt[p[i]] += 143ans = 044while mx:45 for i in depid[mx]:46 if f[i]:47 if cnt[i] <= f[i]:48 f[i] -= cnt[i]49 ans += cnt[i]50 else:51 ans += f[i]52 f[i] = 053 f[fa[i]] += f[i]54 mx -= 155write(ans, '\n')
P5197 [USACO19JAN] Grass Planting S
一个点的相邻的点都不能是同一颜色,如果算上自己有 $n$ 个颜色,那就至少要 $n$ 个颜色。
定义每个点的度为 d[i]
,取 d[i] + 1
的最大值就是答案吗?答案是肯定。设最大值为 $t$,则先随便涂一个点 $i$ 的相邻点,以它为根继续考虑孩子颜色,发现对于每个孩子来说只有 $2$ 个颜色被确定了,从剩下 $t - 2$ 个颜色中任意选一些不同的颜色来涂孩子,以此递归就可以。
1x = 02y = 03ans = 04n = 05deg = [0] * 1000076
7n = int(input())8for i in range(1, n):9 x, y = map(int, input().split())10 deg[x] += 1 # 统计度数11 deg[y] += 112 if deg[x] > ans:13 ans = deg[x] + 114 if deg[y] > ans:15 ans = deg[y] + 12 collapsed lines
16
17print(ans + 1)
P7148 [USACO20DEC] Cowntagion S
首先,对于每一个节点,如果它的感染者数目已经超过了儿子数,则进行的一定是儿子个数次 (2) 操作。
反之,如果在还没有足够的感染者个数的情况下就开始分,显然是不优的。
所以对于每一个节点都进行贪心:
- 如果还不够分,就执行若干次 (1) 操作,直到够分了为止。
- 如果已经够分了,就花若干天,每天执行一次 (2) 操作直到所有儿子都有感染者为止。
很容易证明这是最优的。
于是我们记录每一个节点的儿子个数,记为 cson[u]cson[u],每次 dfsdfs 到一个点,我们就先计算 logcson[u]+1logcson[u]+1,表示自增至足够感染者的天数(注意不是 ceil),然后进行分发,即花 cson[u]cson[u] 天给所有儿子都发一个感染者,最后注意根节点本身就有一只感染者,处理一下即可。