D.双倍快乐
题意
给出一个n个点的树(n-1条边)
每个点有一个权值val[i]
每条边有一个属性0/1
定义一个点的快乐值为它的子节点的快乐值+它自身的权值
当且仅当一个点既有1又有0 的边时它自身的权值会翻倍
于是它的快乐值=它的子节点的快乐值+它自身的权值×2
现在最多改变一个边的属性 0变1 ，1变0
问所有点的快乐值和最大是多少
题解
注意到题目中翻倍的是自身权值 而不是它的快乐值
所以可以将翻倍的贡献独立出来计算
将一个点对总的贡献值看作
(它的子节点贡献+它自身的权值) 和 (修改某边使节点权值翻倍的贡献)
对于前者可直接通过dfs求得
对于后者则枚举修改那一条边能产生的贡献最大
注意改变一条边的属性可能会使两个点翻倍
观察发现 对于一个点i若改变一条边能使得它自身的权值 翻倍
那么它翻倍部分(即多加了val[i])对总快乐值的贡献为deep[i]×val[i]
(因为它的权值将会作为父节点快乐值的一部分向上传递)
于是枚举修改边 计算翻倍产生贡献最大的 更新答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e5+5;
const double Pi=acos(-1);
const ll mod=1e9+7;
ll val[Max],d[Max];
bool doub[Max],can[Max];
int cnt[2][Max],deep[Max];
vector<pair<int,int> >mp[Max];
void dfs_val(int now,int fa){
for(auto i:mp[now]){
if(fa==i.first)continue;
//deep[i.first]=deep[now]+1;
dfs_val(i.first,now);
val[now]+=val[i.first];
}
}
void dfs_deep(int now,int fa){
for(auto i:mp[now]){
if(fa==i.first)continue;
deep[i.first]=deep[now]+1;
dfs_deep(i.first,now);
//val[now]+=val[i.first];
}
}
int main(){
//Turnoff;
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>d[i];
val[i]=d[i];
}
for(int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
mp[u].push_back({v,w});
mp[v].push_back({u,w});
}
for(int i=1;i<=n;i++){
int cnt1=0,cnt0=0;
for(auto edge:mp[i]){
if(edge.second)cnt[1][i]++;
else cnt[0][i]++;
}
}
deep[1]=1;dfs_deep(1,0);ll ans=0,change=0;
for(int i=1;i<=n;i++){
if(cnt[0][i]&&cnt[1][i])val[i]*=2;
}
dfs_val(1,0);
for(int i=1;i<=n;i++)ans+=val[i];
for(int i=1;i<=n;i++){
for(auto edge:mp[i]){
ll temp=0;int to=edge.first;
if(edge.second){
temp-=(cnt[1][i]&&cnt[0][i])*d[i]*deep[i];
temp-=(cnt[1][to]&&cnt[0][to])*d[to]*deep[to];
cnt[1][i]--;cnt[0][i]++;
cnt[1][to]--;
cnt[0][to]++;
temp+=(cnt[1][i]&&cnt[0][i])*d[i]*deep[i];
temp+=(cnt[1][to]&&cnt[0][to])*d[to]*deep[to];
cnt[1][i]++;cnt[0][i]--;
cnt[1][to]++;
cnt[0][to]--;
}
else{
temp-=(cnt[1][i]&&cnt[0][i])*d[i]*deep[i];
temp-=(cnt[1][to]&&cnt[0][to])*d[to]*deep[to];
cnt[0][i]--;cnt[1][i]++;
cnt[0][to]--;
cnt[1][to]++;
temp+=(cnt[1][i]&&cnt[0][i])*d[i]*deep[i];
temp+=(cnt[1][to]&&cnt[0][to])*d[to]*deep[to];
cnt[0][i]++;cnt[1][i]--;
cnt[0][to]++;
cnt[1][to]--;
}
change=max(change,temp);
}
}
//cout<<ans<<" "<<change<<endl;
cout<<ans+change<<endl;
}
|