[ICPC2021 Nanjing R] Crystalfly
传送门?
题面翻译
给定一个 n ( 1 ≤ n ≤ 1 05)n(1\le n\le10^5)n(1≤n≤105) 个节点的树,每个节点上有 ai a_iai 只晶蝶。派蒙最初在 111 号节点,并获得 111 号节点的所有晶蝶,接下来每一秒她可以移动到相邻的节点上并获得节点上的所有晶蝶,但是当她每到达一个节点 uuu 后,对于每个与 uuu 相邻的节点 vvv,节点 vvv 上的的晶蝶会在 tv( 1 ≤ tv≤ 3 )t_v(1\le t_v\le3)tv(1≤tv≤3) 秒内消失,在 tv t_vtv 秒后再到达节点 vvv 将无法获得节点上的晶蝶。现在需要你求出最多可以获得的晶蝶数。
题目描述
Paimon is catching crystalflies on a tree, which are a special kind of butterflies in Teyvat. A tree is a connected graph consisting of nnn vertices and ( n − 1 )(n – 1)(n−1) undirected edges.
There are initially ai a_iai crystalflies on the iii-th vertex. When Paimon reaches a vertex, she can catch all the remaining crystalflies on the vertex immediately. However, the crystalflies are timid. When Paimon reaches a vertex, all the crystalflies on the adjacent vertices will be disturbed. For the iii-th vertex, if the crystalflies on the vertex are disturbed for the first time at the beginning of the t′ t’t′-th second, they will disappear at the end of the ( t′+ ti)(t’ + t_{i})(t′+ti)-th second.
At the beginning of the 000-th second, Paimon reaches vertex 111 and stays there before the beginning of the 111-st second. Then at the beginning of each following second, she can choose one of the two operations:
- Move to one of the adjacent vertices of her current vertex and stay there before the beginning of the next second (if the crystalflies in the destination will disappear at the end of that second she can still catch them).
- Stay still in her current vertex before the beginning of the next second.
Calculate the maximum number of crystalflies Paimon can catch in 1 0 1 0 1 0 1 01010^{10^{10^{10^{10}}}}1010101010 seconds.
输入格式
There are multiple test cases. The first line of the input contains an integer TTT indicating the number of test cases. For each test case:
The first line contains an integer nnn ( 1 ≤ n ≤ 1 05 1 \le n \le 10^51≤n≤105) indicating the number of vertices.
The second line contains nnn integers a1, a2, ⋯ , an a_1, a_2, \cdots, a_na1,a2,⋯,an ( 1 ≤ ai≤ 1 09 1 \le a_i \le 10^91≤ai≤109) where ai a_iai is the number of crystalflies on the iii-th vertex.
The third line contains nnn integers t1, t2, ⋯ , tn t_1, t_2, \cdots, t_nt1,t2,⋯,tn ( 1 ≤ ti≤ 31 \le t_i \le 31≤ti≤3) where ti t_iti is the time before the crystalflies on the iii-th vertex disappear after disturbed.
For the next ( n − 1 )(n – 1)(n−1) lines, the iii-th line contains two integers ui u_iui and vi v_ivi ( 1 ≤ ui, vi≤ n1 \le u_i, v_i \le n1≤ui,vi≤n) indicating an edge connecting vertices ui u_iui and vi v_ivi in the tree.
It’s guaranteed that the sum of nnn of all the test cases will not exceed 1 06 10^6106.
输出格式
For each test case output one line containing one integer indicating the maximum number of crystalflies Paimon can catch.
样例 #1
样例输入 #1
251 10 100 1000 100001 2 1 1 11 21 32 42 551 10 100 1000 100001 3 1 1 11 21 32 42 5
样例输出 #1
1010110111
提示
For the first sample test case, follow the strategy below.
- During the 00 0-th second
- Paimon arrives at vertex 11 1;
- Paimon catches 11 1 crystalfly;
- Crystalflies in vertices 22 2 and 33 3 are disturbed.
- During the 11 1-st second
- Paimon arrives at vertex 33 3;
- Paimon catches 100100 100 crystalflies.
- During the 22 2-nd second
- Paimon arrives at vertex 11 1;
- Crystalflies in vertex 22 2 disappears.
- During the 33 3-rd second
- Paimon arrives at vertex 22 2;
- Crystalflies in vertices 44 4 and 55 5 are disturbed.
- During the 44 4-th second
- Paimon arrives at vertex 55 5;
- Paimon catches 1000010000 10000 crystalflies;
- Crystalflies in vertex 44 4 disappears.
For the second sample test case, the optimal strategy is the same with the first sample test case. Crystalflies in vertex 222 are scheduled to disappear at the end of the 333-rd (instead of the 222-nd) second, allowing Paimon to catch them.
以上来自洛谷以上来自洛谷以上来自洛谷
解题思路
好好看题,就知道是树形 d pdpdp。定义 f u , 0 或 1 f_{u,0或1}fu,0或1 为遍历以 uuu 为根的整棵子树且 uuu 点的子节点的晶蝶消失( f u , 0 f_{u,0}fu,0)或不消失( f u , 1 f_{u,1}fu,1)的情况下所能获得的最大晶蝶数量。记与 uuu 相邻的非父亲节点中 ti= 3t_i=3ti=3 的节点晶蝶数量的最大值和第二大值分别为 m a x 1 , m a x 2max1,max2max1,max2,若不存在特判即可。
如果当前节点不存在 ti= 3t_i=3ti=3 的节点,则 f u , 0= ( Σ f v , 1( v ∈ s o nu) ) + m a x ( av) + f u , 1= Σ f v , 1( v ∈ s o nu)f_{u,0}=(\Sigma f_{v,1}(v\in son_u))+max(a_v)+f_{u,1}=\Sigma f_{v,1}(v\in son_u)fu,0=(Σfv,1(v∈sonu))+max(av)+fu,1=Σfv,1(v∈sonu)。
如果当前节点存在 ti= 3t_i=3ti=3 的节点,那么通过手动画图观察发现,记所有子节点的 f v , 1 f_{v,1}fv,1 的和 Σ f v , 1( v ∈ s o nu)\Sigma f_{v,1}(v\in son_u)Σfv,1(v∈sonu)为 s u msumsum, f u , 0 f_{u,0}fu,0 结果不变, f u , 1= max ( f v , 0+ av+ s u m − f v , 1+ m a x 1 , f v , 0+ av+ s u m − f v , 1+ m a x 2 )f_{u,1}=\max(f_{v,0}+a_v+sum−f_{v,1}+max1,f_{v,0}+a_v+sum−f_{v,1}+max2)fu,1=max(fv,0+av+sum−fv,1+max1,fv,0+av+sum−fv,1+max2)
最后的答案为 f 1 , 1+ a1 f_{1,1}+a_1f1,1+a1。
AC Code
#include using namespace std;#define int long longconst int Maxn = 1e5 + 5;vector<int> g[Maxn];int n, u, v;int a[Maxn];int f[Maxn], sum[Maxn], t[Maxn];inline void dfs(int u, int fa) {int maxx = 0;multiset<int> st;for (int v : g[u]) {if (v == fa) {continue;}dfs(v, u);sum[u] += f[v];maxx = max(maxx, a[v]);if (t[v] == 3) {st.insert(a[v]);}}f[u] = sum[u] + maxx;st.insert(LONG_LONG_MIN);for (int v : g[u]) {if (v == fa) {continue;}if (t[v] == 3) {st.erase(st.find(a[v]));}f[u] = max(f[u], sum[u] - f[v] + a[v] + sum[v] + *st.rbegin());if (t[v] == 3) {st.insert(a[v]);}}}inline void solve() {cin >> n;for (int i = 1; i <= n; i++) {g[i].clear();f[i] = sum[i] = 0;}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 - 1; i++) {cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}dfs(1, 0);cout << f[1] + a[1] << endl;}inline void work() {int T;cin >> T;while (T--) {solve();}}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);work();return 0;}