题解 P6554 【Promises I Can't Keep】
Diaоsi
·
·
题解
Promises I Can't Keep
二次扫描+换根 dp
首先将问题转换，由于电流是等概率地流向任意一个叶子节点，所以对于任意一个节点，只需要求出该节点到叶子节点的所有的路径上的点权的总和，再除以该节点能到达的叶子节点的数量，即可求得最终答案。
考虑一个暴力点的做法，对于一个非叶子节点，如何计算该节点到叶子节点的所有的路径上的点权的总和。
考虑使用树形 dp
对于节点 x ，设该点的点权为 w(x) 。
考虑如下转移：
$$F(x) = \sum_{y\in Son(x)} w(x) \cdot leaf(y) + F(y)$$
$$leaf(x) = \sum_{y\in Son(x)} leaf(y)$$
考虑边界条件，当且仅当 $x$ 节点为叶子节点：
$$F(x) = w(x),leaf(x)=1$$
如何解释这个转移方程呢，$F(y)$ 表示以 $y$ 节点为根的子树的答案，显然经由节点 $y$ 到节点 $x$ 的路径数为以 $y$ 为根的子树的叶子节点数。
显然该子树对 $F(x)$ 的**贡献**即为 $w(x) \cdot leaf(y)$ 。
计算完 $F(x)$ 的结果后，考虑如何通过 $F(x)$ 去计算其他节点的答案。
以题目中的样例为例：
此时：
+ $F(x)$ 表示 $x$ 节点到叶子节点的所有的路径上的点权的总和。
+ $F(y)$ 表示 $y$ 节点到以 $y$ 为根的子树中的叶子节点的所有的路径上的点权的总和。
设：
+ $w(x)$ 表示 $x$ 节点的点权。
+ $leaf(x)$ 表示 $x$ 节点能到达的叶子节点的数量。
+ $root$ 表示任意指定的根节点，根据题目要求，为简便计算， $root$ 指定为任意一个**非叶子节点**。
接下来考虑如何计算以 $y$ 为根时 $y$ 节点到所有叶子节点的所有的路径上的点权的总和。
当以 $y$ 为根且 $y$ 不为叶子节点时，只需要将 $F(y)$ 与**当以 $y$ 为根时， $x$ 节点到以 $x$ 为根的子树中的叶子节点的所有的路径上的点权的总和**（即下图中的红圈部分）进行合并：
红圈中的部分可以表示为：
$$F(x)-F(y)-leaf(y) \cdot w(x)$$
该方程可以这样解释：从 $x$ 节点出发到以 $y$ 为根的子树中的叶子节点的路径总和为 $F(y)+leaf(y) \cdot w(x)$ ，容斥一下即可正确表示红圈部分。
那如何考虑 $x$ 对 $y$ 的贡献呢？显然 $x$ 对 $y$ 的贡献为**以 $x$ 为根的子树中叶子节点的数量**乘上 $w(y)$ 。
上面加粗的内容显然可以用 $leaf(root)-leaf(y)$ 来表示。
贡献即为：
$$(leaf(root)-leaf(y)) \cdot w(y)$$
将上述方程与 $F(y)$ 合并，可得：
$$F(y)=F(x)-F(y)-leaf(y)\cdot w(x)+(leaf(root)-leaf(y))\cdot w(y)+F(y)$$
当 $y$ 为叶子节点时，由于不能从叶子节点走到叶子节点，所以只需要减去自己相应的贡献即可：
$$F(y)=F(x)-F(y)-leaf(y)\cdot w(x)+(leaf(root)-leaf(y))\cdot w(y)$$
出于方便叙述，上述等式中**左边的 $F(y)$ 表示以 $y$ 为根时 $y$ 节点到所有叶子节点的所有的路径上的点权的总和**，右边的 $F(y)$ **表示 $y$ 节点到以 $y$ 为根的子树中的叶子节点的所有的路径上的点权的总和**。
由于每个节点到其能到的叶子节点的概率是相等的，所以最终的答案就是：
$$\max\{\dfrac{F(x)}{leaf(root)}\},deg_x>1$$
$$\max\{\dfrac{F(x)}{leaf(root)-1}\},deg_x=1$$
到这里这道题基本上就结束了，但是毒瘤出题人卡了链的部分分（会爆```long long```），所以我们需要对链的部分分进行特判。
对于一条链，当起点在叶子节点时，链中所有的节点一定都会被经过一次，而当起点为非叶子节点，起点会被经过两次。对于非叶子节点，贪心取权值最大的作为起点即可（显然其他节点作为起点不可能更优）。最终答案两者取最大即可：
$$\max(\sum_{i=1}^n w_i,\dfrac{\sum_{i=1}^n w_i+\max_{i=2}^{n-1}\{w_i\}}{2})$$
既然你能找到这题，我相信你能瞬间做出来的。
```Code:```
```cpp
#include<bits/stdc++.h>
using namespace std;
const long long N=500010,M=5000010,INF=0x3f3f3f3f;
long long head[N],ver[M],Next[M],tot;
long long n,root,d[N],v[N],deg[N];
long double ans=-INF,num,sum,F[N],w[N],leaf[N];
inline long double Max(long double x,long double y){return x>y?x:y;}
inline long double Min(long double x,long double y){return x<y?x:y;}
void add(long long x,long long y){
ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void dfs1(long long x,long long fa){
bool flag=0;
for(long long i=head[x];i;i=Next[i]){
long long y=ver[i];
if(y==fa)continue;
dfs1(y,x);flag=1;
leaf[x]+=leaf[y];
F[x]+=(w[x]*leaf[y])+F[y];
}
if(!flag){
leaf[x]=v[x]=1;
F[x]=w[x];++num;
}
}
void dfs2(long long x,long long fa){
for(long long i=head[x];i;i=Next[i]){
long long y=ver[i];
if(y==fa)continue;
if(!v[y])F[y]=(F[x]-leaf[y]*w[x]+(num-leaf[y])*w[y]);
else F[y]=(F[x]-F[y]-leaf[y]*w[x]+(num-leaf[y])*w[y]);
dfs2(y,x);
}
F[x]/=(v[x])?num-1.0:num;
ans=Max(ans,F[x]);
}
void solve(){
for(long long i=2;i<n;i++)
ans=Max(ans,w[i]);
printf("%.4lf",(double)Max(sum,(sum+ans)/2.0));
}
int main(){
scanf("%lld",&n);
for(long long i=1;i<n;i++){
long long x,y;
scanf("%lld%lld",&x,&y);
add(x,y),add(y,x);
++deg[x],++deg[y];
if(deg[x]>1)root=x;
if(deg[y]>1)root=y;
}
for(long long i=1;i<=n;i++)
scanf("%Lf",&w[i]),sum+=w[i];
dfs1(root,0);
if(leaf[root]==2){solve();return 0;}
dfs2(root,0);
printf("%.4lf",(double)ans);
return 0;
}
```