题解 P6513 【[QkOI#R1] Quark and Tree】

· · 题解

首先不考虑加边，若仅计算以某个点为根时树中所有点的深度与点权乘积之和，可以用换根 DP 处理。

指定 u 为基环树环上的一个点，且不是新加的边的端点，将其提为树根。

设以 u 为根时，i 在树中的父节点为 f_i，以点 i 为根的子树中所有点的点权和为 s_i，\operatorname{dis}(i,j) 为树上点 i 与点 j 的距离，dep_i=dis(u,i)。

下面给出一棵树为例：

为保证 u 在环上，取位于不同子树中的 v,w 两点连边，如下图所示：

则所有点在基环树中的深度变为它到环上的点的最短距离，可以发现离一个点最近的环上的点必然是其本身或其祖先节点中在环上的深度最深的点。这里设离点 i 最近的环上的点为 d_i，则基环树中点 i 的深度相比原先在树中的深度减少 \operatorname{dis}(u,i)-\operatorname{dis}(d_i,i)=\operatorname{dis}(u,d_i)=dep_{d_i}，故对答案的贡献相比原先减少 w_i dep_{d_i}。

考虑将 d_i 相同的点一起计算。设环上的点集为 S，则对答案的贡献减少量形如 \sum_{i\in S} t_i dep_i，其中 t_i=\sum_{j=1}^{n}[d_j=i]w_j。接下来考虑 d_i 相同的点的条件。设环上有一点对 (x,y)，满足在原先的树中 x 是 y 的父节点，则若以 x 为根的子树中的一点 i 满足 d_i \neq x，当且仅当它是以 y 为根的子树中的点，故 t_x=s_x-s_y。考虑到点 u 在树中没有父节点，且 dep_u=0，故 d_i=u 的点不对答案的减少造成影响。将上式 s_x-s_y 中 -s_y 的贡献移至点 y 进行计算，可得出答案贡献减少量为 \sum_{i \in S \land i \neq u} s_i dep_i-s_i dep_{f_i}，由于父子节点深度差为 1，故最终得出的贡献减少量为 \sum_{i \in S \land i \neq u} s_i。

所以最终的问题就是找出两条与 u 相连且无重叠部分的两条链，满足两条链上所有点的 s_i 之和最小，同样也可以用类似于换根 DP 的方法处理。

最终只需要枚举点 u，利用换根 DP 得到的信息求出以 u 为根的树的答案。假设以 u 为根时树中所有点的深度与点权乘积之和为 t_u，满足上述条件的两条链上所有点的 s_i 之和为 l_u（这里的两条链不包括点 u），则以 u 为根的树的答案为 t_u-l_u，取最小值即可。

时间复杂度 O(n)。

代码：

//似乎挺多人反映细节多qwq，但出题人感觉这么想细节并不会太多？
#include <cstdio>
#include <cctype>
#include <cstring>
#define MaxN (1000005)
using namespace std;
typedef long long ll;
void Read(int &x){
    static char c;
    static int f;
    f=1;
    while(!isdigit(c=getchar()))
        if(c=='-')
            f=-1;
    x=(c^48);
    while(isdigit(c=getchar()))
        x=x*10+(c^48);
    x*=f;
    return;
}
void Print(ll x){
    if(x<0)
        putchar('-'),x=-x;
    static ll i;
    for(i=1;i*10LL<=x;i*=10);
    for(;i;i/=10)
        putchar(x/i%10|48);
    putchar('\n');
    return;
}
inline ll mmax(ll a,ll b){return a>b?a:b;}
inline ll mmin(ll a,ll b){return a<b?a:b;}
struct LnkNode{
    int v,nxt;
}edge[MaxN*2];
int etot,fst[MaxN];
inline void addedge(int u,int v){
    ++etot;
    edge[etot].v=v;
    edge[etot].nxt=fst[u];
    fst[u]=etot;
    return;
}
int n,w[MaxN],s[MaxN];
ll d[MaxN],dm[MaxN],sdm[MaxN],res=-9223372036854775807LL;
void dfs1(int x,int f){
    s[x]=w[x];
    ll t;
    for(int i=fst[x];i;i=edge[i].nxt)
        if(edge[i].v!=f){
            dfs1(edge[i].v,x);
            s[x]+=s[edge[i].v];
            d[x]+=d[edge[i].v]+s[edge[i].v];
            t=s[edge[i].v]+mmin(dm[edge[i].v],0);
            if(t<dm[x])
                sdm[x]=dm[x],dm[x]=t;
            else if(t<sdm[x])
                sdm[x]=t;
        }
    return;
}
void dfs2(int x,int f){
    if(f){
        d[x]=d[f]+s[1]-s[x]*2;
        ll t=s[1]-s[x]+mmin((dm[f]!=s[x]+mmin(dm[x],0))?(dm[f]):(sdm[f]),0);
        if(t<dm[x])
            sdm[x]=dm[x],dm[x]=t;
        else if(t<sdm[x])
            sdm[x]=t;
    }
    if(sdm[x]!=0x3f3f3f3f3f3f3f3fLL && d[x]-dm[x]-sdm[x]>res)
        res=d[x]-dm[x]-sdm[x];
    for(int i=fst[x];i;i=edge[i].nxt)
        if(edge[i].v!=f)
            dfs2(edge[i].v,x);
    return;
}
int main(){
    int a,b;
    Read(n);
    memset(dm+1,0x3f,sizeof(ll)*n);
    memset(sdm+1,0x3f,sizeof(ll)*n);
    for(int i=1;i<=n;++i)
        Read(w[i]);
    for(int i=1;i<n;++i){
        Read(a);
        Read(b);
        addedge(a,b);
        addedge(b,a);
    }
    dfs1(1,0);
    dfs2(1,0);
    Print(res);
    return 0;
}