跳转至

UOJ105

UOJ105 Beads and wiresψ(｀∇´)ψ

一道个人认为非常棒的题，卡了我接近一天的时间。

虽然YL怒斥这题套路 ，不过他也说这题想起来容易，推起来一般，实现很恶心（

\(\text{Decription}\)ψ(｀∇´)ψ

问题：你有 \(n\) 个珠子，初始你可以选任意的一个珠子，之后可以执行以下的操作： 1. 把一颗新的珠子 \(v\) 和已经选了的某一个珠子 \(u\) 用红色边 (u,v) 相连。 2. 把一颗新的珠子 \(w\) 插入到用红色边链接的两个节点 \(u,v\) 当中，具体来说，将 \(u,w\) 和 \(v,w\) 分别用蓝色边相连，然后删除 \((u,v)\) 这条红色边。 现在给定你所有操作完了之后的情况，并说明两个相互链接的点之间的边权，但是你不知道边的颜色。 要你找到一种可能的方案使得你的得分最大，定义你的得分为所有操作完了之后的蓝色边权值之和。 输出这个最大的得分。\(n \le 5\times 10^5\)。

\(\text{Solution}\)ψ(｀∇´)ψ

首先我们可以发现，最后给出的情况一定是一颗无根的带权树。

然后发现蓝色的边一定是一条由三个连续节点和链接他们的两条边构成的一条链。

注意到题目中说蓝色边只能在红色边的基础上“插入”来生成。

也就是说，如果现在钦定一条蓝色链 \((u,v,w)\) 且 \(w\) 是被插入到 \((u,v)\) 的那个节点，\(w\) 一定不能是另外一条蓝色链中被“插入”的点（我们称这个点为蓝色链的中点）。

所以，如果两条蓝色的链有重叠部分，无非两种情况：

  1. 这两条链当中分别有一个端点和另外一条链的那个端点是相连的（两端相交）。
  2. 这两条链当中有一个条链的中点是另外一条链的端点（也就是没有一个节点是同时做两条蓝色链的端点的）。

根据这个性质，我们可以先推出假定了一个根节点的时候的答案，并考虑一个 \(\text{O}(n^2)\) 的做法（每个点跑一次 dfs）。

假设 \(f_{u,0/1}\) 表示 \(u\) 不是/是一条蓝色链的中点，在以 \(u\) 为根的子树当中能获得的最大分数。

\(f_{u,0}\) 很好推，既然它不是一条蓝色链的中点，并且现在是在 \(u\) 的子树当中考虑，那么我们枚举 \(u\) 的每一个儿子为中点的情况进行转移即可，当然不要忘记考虑 \(u\) 和 \(v\) 连的是红色边的情况。

\(f_{u,0}=\sum \max(f_{v,0},f_{v,1}+w_{u,v})\)

\(f_{u,1}\) 也很好考虑，因为 \(u\) 只能是一条蓝色链的中点，所以我们只需要枚举作为这一条蓝色链的端点的儿子 \(v\) ，其他的儿子可以用 \(u\) 不是中点的情况转移（根据上面的情况2）。

所以转移的时候可以利用 \(f_{u,0}\) 扣掉当前儿子 \(v\) 在 \(f_{u,0}\) 当中做的贡献 \(\max(f_{v,0},f_{v,1}+w_{u,v})\)，再加上 \(v\) 在当前情况做的贡献 \(f_{v,0}+w_{u,v}\)。

\(f_{u,1}=f_{u,0}+\max\{f_{v,0}+w_{u,v}-\max(f_{v,0},f_{v,1}+w_{u,v})\}\)

好，现在我们对每一个点为根的情况都做一次DP，就可以拿到 57pts 的好成绩了。

发现这个做法非常符合换根DP的形式，根节点的变化会对答案造成影响，并且暴力做法是对于每一个根进行DP。

所以考虑把原本 \(\text{O}(n)\) 的暴力换根优化到 \(\text{O}(1)\)。

现在，假设根从父亲节点 \(u\) 变成了儿子节点 \(v\) ，会有什么影响呢？

明显，\(v\) 在第一次 dfs 的时候对 \(u\) 的贡献没有了，而转移方程里面又有最大值。

所以我们为了转移，需要记录次大值（这是一个很经典的 trick）。也就是在抛掉 \(v\) 之后，在 \(u\) 的儿子当中贡献最大的那一个。

因为换根之后，\(u\) 会变成 \(v\) 的父亲，那么相对的，从 \(u\) 的状态转移到 \(v\) ，计算 \(u\) 现在对 \(v\) 的贡献时，需要去除 \(v\) 给 \(u\) 的贡献，直接做加减法不好维护，所以我们考虑直接维护扣掉贡献之后的值。

我们设 \(dp_{u,0/1,v}\) 表示在转移 \(f_{u,0/1}\) 这个状态的时候，不考虑以 \(v\) 为根的子树 ，在 \(u\) 的子树当中可以获得的最大分数。

因为在 \(f_{u,0}\) 这个状态的时候，\(v\) 的贡献就是 \(\max(f_{v,0},f_{v,1}+w_{u,v})\) ，并且 \(f_{u,0}\) 是对每个儿子的贡献求和，所以不涉及到最大值变化的问题，直接在 \(f_{u,0}\) 当中减去即可。

\(dp_{u,0/1,v}=f_{u,0}-\max(f_{v,0},f_{v,1}+w_{u,v})\)

而考虑 \(f_{u,1}\) 的时候，\(v\) 有可能给 \(f_{u,1}\) 贡献最大的 \(f_{v,0}+w_{u,v}-\max(f_{v,0},f_{v,1}+w_{u,v})\)。

所以还需要记录最大值次大值来进行转移。

\(dp_{u,0/1,v}=\begin{cases} dp_{u,0,v}+max_1 & \text{trans}_v \ \text{is not the max contribute}\\ dp_{u,0,v}+max_2 & \text{otherwise.}\end{cases}\)

其中 \(trans_v=f_{v,0}+w_{u,v}-\max(f_{v,0},f_{v,1}+w_{u,v})\)

\(max_1,max_2\) 是在第一次 dfs 的时候记录的 \(u\) 所有的儿子 \(trans_v\) 的最大值和次大值。

然后换根的时候枚举每一个点的儿子，先把 \(f_{u,0} = dp_{u,0,v},f_{u,1} = dp_{u,1,v}\)。

然后重新计算 \(u\) 对 \(v\) 的贡献（换根），不过因为 \(fa\) 在当前情况变成了 \(u\) 的儿子，所以我们需要先把 \(fa\) 对 \(u\) 的贡献计算出来。

计算完了之后在答案里取个最大值即可。

\(\text{Code}\)ψ(｀∇´)ψ

实现 
 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
#include<bits/stdc++.h>
using namespace std;

constexpr int si=5e5+10;
constexpr int inf=0x3f3f3f3f;
int n;
struct Tree{
    int head,ver,Next,w;
}e[si<<1];
int tot=0;
inline void add(int u,int v,int w){
    e[++tot].ver=v,e[tot].Next=e[u].head;
    e[tot].w=w,e[u].head=tot;
}
int father[si],len[si]; // father 和 len 是方便 dfs2 的转移用的。
int f[si][2];
std::vector<int>son[si]; // 记录儿子，便于转移
std::vector<int>dp[si][2];
std::vector<int>mx[si]; // 记录 u 的每一个儿子的 trans，如果当前儿子的 trans 是最大的，那么替换成次大值再计算。

inline void dfs1(int u,int fa){
    int max1,max2; max1=max2=-inf;
    f[u][0]=0,f[u][1]=-inf;
    for(register int i=e[u].head;i;i=e[i].Next){
        int v=e[i].ver,w=e[i].w;
        if(v==fa) continue;
        len[v]=w,father[v]=u,son[u].push_back(v); // 记录信息
        dfs1(v,u),f[u][0]+=max(f[v][0],f[v][1]+w); // 转移
        int trans=f[v][0]+w-max(f[v][0],f[v][1]+len[v]);
        if(trans>max1) max2=max(max2,max1),max1=trans;
        else max2=max(trans,max2); // 记录次大值。
    } f[u][1]=f[u][0]+max1;
    for(register int i=e[u].head;i;i=e[i].Next){
        int v=e[i].ver,w=e[i].w;
        if(v==fa) continue;
        dp[u][0].push_back(f[u][0]-max(f[v][0],f[v][1]+w));
        int trans=f[v][0]+w-max(f[v][0],f[v][1]+len[v]);
        if(trans==max1) dp[u][1].push_back(dp[u][0].back()+max2),mx[u].push_back(max2);
        else dp[u][1].push_back(dp[u][0].back()+max1),mx[u].push_back(max1);
    } return ;
} int res=0;
inline void dfs2(int u){
    for(register unsigned i=0;i<son[u].size();++i){
        f[u][0]=dp[u][0][i],f[u][1]=dp[u][1][i];
        if(father[u]){
            f[u][0]+=max(f[father[u]][0],f[father[u]][1]+len[u]);
            f[u][1]=f[u][0]+max(mx[u][i],f[father[u]][0]+len[u]-max(f[father[u]][0],f[father[u]][1]+len[u]));
            // 每次都需要再算一遍（当然也可以只算一次然后记下来）
            // 现在为了计算 fa 对 u 的贡献，先把 u 暂时当作根节点，从它的父亲和原来的儿子当中转移。
            // 相当于是把 fa 添加到了 u 的儿子当中，再跑一次类似 dfs1 里面的 dp 的过程来更新。
        } res=max(res,f[son[u][i]][0]+max(f[u][0],f[u][1]+len[son[u][i]])); // 记录当前情况的答案
        dfs2(son[u][i]);
    } return ;
}

int main(){
    scanf("%d",&n);
    for(register int i=1,u,v,w;i<n;++i){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w),add(v,u,w);
    } dfs1(1,0),dfs2(1);
    return printf("%d\n",res),0;
}

记录最大值和次大值的时候也可以利用std::multiset，把从下到上的时候把所有 \(trans\) 扔进去，然后从上到下转移的时候判当前的 \(trans\) 是不是 multiset 当前的最大值就可以，如果是，那么删除这个值并用次大值更新，反之直接用最大值更新即可。

不过复杂度会多一个 \(\log\)。

1
Tag : 树/树形DP/换根DP
最后更新: May 9, 2023