The 2021 ICPC Asia Nanjing Regional Contest H.Crystalfly(树上DP)
有一个容易被忘记的坑点:
在我们锁定最大点w,然后对其他点进行第二种决策的计算时,要记得还要反过来拿其他店对w点进行一轮第二种决策的计算!!!
还有别忘了if(i==fa)continue!!!
另外vector里的pair的second是没有用的,可以忽略
#include <bits/stdc .h>
#define int long long
#define endl '\n'
using namespace std;
int n;
const int N = 1e5 10;
int a[N];
int t[N];
vector<pair<int, int>>g[N];
int sum[N], f[N];
void dfs(int u, int fa) {
int aim = 0;
int t1 = 0, t2 = 0;
if (g[u].size() == 1 && fa != -1) {
return;
}
for (auto i : g[u]) {
if (i.first == fa)
continue;
dfs(i.first, u);
sum[u] = f[i.first];
}
for (auto i : g[u]) {//第一种决策
if (i.first == fa)
continue;
t1 = max(t1, sum[u] a[i.first]);
}
int maxw = 0, w = 0;
for (auto i : g[u]) {//找到w
if (i.first != fa && t[i.first] == 3 && a[i.first] > maxw) {
maxw = a[i.first];
w = i.first;
}
}
if (w != 0)
for (int j = 0; j < g[u].size(); j ) {//用w对其他点一轮转移
if (g[u][j].first == fa)
continue;
int v = g[u][j].first;
if (w == v)
continue;
t2 = max(t2, sum[u] - f[v] a[v] sum[v] a[w]);
}
for (int j = 0; j < g[u].size(); j ) {//还要其他点对w进行一轮转移
if (g[u][j].first == fa)
continue;
int v = g[u][j].first;
if (v == w)
continue;
if (t[v] == 3) {
t2 = max(t2, sum[u] - f[w] a[w] sum[w] a[v]);
}
}
f[u] = max(t1, t2);
}
void init() {
for (int i = 1; i <= n; i ) {
f[i] = 0;
sum[i] = 0;
}
for (int i = 1; i <= n; i )
g[i].clear();
}
void solve() {
cin >> n;
init();
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 ) {
int u, v;
cin >> u >> v;
g[u].push_back({v, a[v]});//没有意义
g[v].push_back({u, a[u]});
}
dfs(1, -1);
cout << f[1] a[1] << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfebab
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01