Steven_MengのBlog

这题真的很套路,很没意思。

考虑换根dp,然后就是爆拆式子:

($A$为除去$u$之后的$u$子树,$B$为除去$v$之后的$v$子树)

以$u$为根:

$\sum _{i\in A}dis(i,u)^2 c[i]+w^2c[v]+\sum _{i\in B}dis(i,u)^2c[i]$

以$v$为根:

$\sum_{i\in A}dis(i,v)^2c[i]+w^2c[u]+\sum _{i\in B}dis(i,v)^2c[i]$

注意到$i\in A$时,$dis(i,u)=dis(i,v)+w$,

$i\in B$时,$dis(i,u)=dis(i,v)-w$。

然后就是爆拆式子:

第一部分的$Delta1$

$\sum _{i \in A} dis(i,u)^2 c[i]-\sum_{i\in A}dis(i,v)^2c[i]$

$=\sum _{i \in A} (dis(i,v)+w)^2 c[i]-\sum_{i\in A}dis(i,v)^2c[i]$

$=\sum _{i \in A} (dis(i,v)^2+2w \times dis(i,v)+w^2)c[i]-\sum_{i\in A}dis(i,v)^2c[i]$

$=2w \times \sum_{i\in A} dis(i,v) c[i]+w^2 \times \sum _{i\in A} c[i]$

然后要维护后面两个值,发现第一个并不是很好维护,于是我们又要再一次换根来求出这个毒瘤东西。

细节部分自己看吧。

考试时因为没有考虑到$1$不一定在$v$子树里面,然后直接用了以$1$为根的子树值,然后调了$1h$才发现,血亏。

第二部分的$Delta2$

长得这个样子,自己推吧:

$-\sum _{i\in B}dis(i,v)c[i]+w^2 \times _{i\in B} c[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
91
92
#include <bits/stdc++.h>
#define MAXN 200005
#define ld long double
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
ld sum_dis_c[MAXN],sum_c[MAXN],asroot[MAXN];
//以u为根的sum_dis_c
ld c[MAXN];
ld Ans,ret;
namespace Tree{
    struct Edge{
        int to;
        ld len;
    };
    vector<Edge>G[MAXN];
    inline void AddEdge(int u,int v,ld w){
        G[u].push_back(Edge{v,w});
    }
    void dfs(int u,int father){//先初始化sum_dis_c[MAXN],sum_c[MAXN]
        for (register int i=0;i<(int)G[u].size();++i){
            int v=G[u][i].to,w=G[u][i].len;
            if (v==father) continue;
            dfs(v,u);
            sum_dis_c[u]+=sum_dis_c[v]+w*sum_c[v];//提起来了w的距离
            sum_c[u]+=sum_c[v];//加上子树的sum_c
        }
        sum_dis_c[u]+=0*c[u];
        sum_c[u]+=c[u];
    }
    void Init(int u,int father,ld Len){
        Ans+=c[u]*Len*Len;
        for (register int i=0;i<(int)G[u].size();++i){
            int v=G[u][i].to,w=G[u][i].len;
            if (v==father) continue;
            Init(v,u,Len+w);
        }
    }
}
using namespace Tree;
void Init2(int u,int father){
    for (register int i=0;i<(int)G[u].size();++i){
        int v=G[u][i].to,w=G[u][i].len;
        if (v==father) continue;
        asroot[v]=asroot[u]-w*sum_c[v]+w*(sum_c[1]-sum_c[v]);
        Init2(v,u);
    }
}
void Solve(int u,int father){
    ret=min(ret,Ans);
    for (register int i=0;i<(int)G[u].size();++i){
        int v=G[u][i].to,w=G[u][i].len;
        if (v==father) continue;
        ld Delta1=2.00*(asroot[u]-sum_dis_c[v]-sum_c[v]*w)*w+(sum_c[1]-sum_c[v]-c[u])*w*w;
        ld Delta2=-2.00*(sum_dis_c[v]+w*sum_c[v]-w*c[v])*w+(sum_c[v]-c[v])*w*w;
        ld Delta=Delta1+Delta2-c[v]*w*w+c[u]*w*w;
        Ans+=Delta;
        Solve(v,u);
        Ans-=Delta;
    }
}
int main(){
    int n=read();
    for (register int i=1;i<=n;++i){
        scanf("%Lf",&c[i]);
    }
    for (register int i=1;i<n;++i){
        int u,v;
        ld w;
        scanf("%d%d%Lf",&u,&v,&w);
        AddEdge(u,v,w);
        AddEdge(v,u,w);
    }
    dfs(1,1);
    Init(1,1,0);
    asroot[1]=sum_dis_c[1];
    Init2(1,1);
    ret=1e23;
    Solve(1,1);
    printf("%.7Lf\n",ret);
}

 评论