【LG3647】[APIO2014]连珠线

【LG3647】[APIO2014]连珠线

题面

洛谷

题解

首先考虑一下蓝线连起来的情况,一定是儿子-父亲-另一个儿子或者是儿子-父亲-父亲的父亲。

而因为一开始只有一个点在当前局面上,将一条红边变为两条蓝边也只能在一对有父子关系的点之间加,所以第一种“儿子-父亲-另一个儿子”的情况实际上是不存在的。

假设我们当前已经选定根节点,设\(f[i][0/1]\)表示当前位于以\(i\)为根的子树\(i\)不作为/作为中转点(即中间的父亲节点)的最大答案。

那么有转移:
\(f[i][0]=\sum_{j\in son_i} max(f[j][0],f[j][1]+cost_{i,j})\)
钦定一个儿子连上来,得到另一部分的转移:
\(f[i][1]=max_{j\in son_i}\{f[i][0]-max(f[j][0],f[j][1]+cost_{i,j})+f[j][1]+cost_{i,j}\}\)

因为根在哪个位置会使我们的情况受到影响,考虑换根。

\(g[i][j][0/1]\)表示当前\(i\)不考虑\(j\)这个儿子和作不作为中转点的最大答案。

那么\(g[i][j][0]\)显然为\(f[i][0]-max(f[j][0],f[j][1]+cost_{i,j})\)

\(g[i][j][1]\)稍微麻烦一些,需要记录转移上来的\(max(f[j][0],f[j][1]+cost_{i,j})+f[j][1]+cost_{i,j}\)最大及次大值,对于从最大值转移上来的儿子,即为次大值的贡献,否则为最大值的贡献。

然后因为这个\(g\)不能直接开数组,所以用\(vector\)代替。

有这个东西就可以偷税的换根了,换根过程详见代码。

代码

#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
#include <cmath> 
#include <algorithm> 
#include <vector> 
using namespace std; 
inline int gi() { 
    register int data = 0, w = 1; 
    register char ch = 0; 
    while (!isdigit(ch) && ch != '-') ch = getchar(); 
    if (ch == '-') w = -1, ch = getchar(); 
    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar(); 
    return w * data; 
}
const int INF = 2e9; 
const int MAX_N = 2e5 + 5; 
struct Graph { int to, cost, next; } e[MAX_N << 1]; 
int fir[MAX_N], e_cnt; 
void clearGraph() { memset(fir, -1, sizeof(fir)); e_cnt = 0; } 
void Add_Edge(int u, int v, int w) { e[e_cnt] = (Graph){v, w, fir[u]}, fir[u] = e_cnt++; } 
int N, fa[MAX_N]; 
int f[MAX_N][2], cost[MAX_N]; 
vector<int> g[MAX_N][3], son[MAX_N], mx[MAX_N]; 
void dfs(int x) { 
    f[x][0] = 0, f[x][1] = -INF; 
    for (int i = fir[x]; ~i; i = e[i].next)
        if (e[i].to != fa[x]) fa[e[i].to] = x, dfs(e[i].to); 
    for (int i = fir[x]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa[x]) continue; 
        son[x].push_back(v), cost[v] = e[i].cost; 
        f[x][0] += max(f[v][0], f[v][1] + e[i].cost); 
    }
    
    int m1 = -INF, m2 = -INF; 
    for (int i = fir[x]; ~i; i = e[i].next) { 
        int v = e[i].to; if (v == fa[x]) continue; 
        int val = f[v][0] + e[i].cost - max(f[v][0], f[v][1] + e[i].cost); 
        f[x][1] = max(f[x][1], f[x][0] + val); 
        if (val > m1) m2 = m1, m1 = val; 
        else if (val > m2) m2 = val; 
    } 
    
    for (int i = fir[x]; ~i; i = e[i].next) { 
        int v = e[i].to; if (v == fa[x]) continue; 
        g[x][0].push_back(f[x][0] - max(f[v][0], f[v][1] + e[i].cost));
        int val = f[v][0] + e[i].cost - max(f[v][0], f[v][1] + e[i].cost); 
        if (val == m1) g[x][1].push_back(g[x][0].back() + m2), mx[x].push_back(m2); 
        else g[x][1].push_back(g[x][0].back() + m1), mx[x].push_back(m1); 
    } 
} 
int ans = 0; 
void rdfs(int x) { 
    for (int i = 0; i < (int)son[x].size(); i++) {
        f[x][0] = g[x][0][i], f[x][1] = g[x][1][i]; 
        if (fa[x]) { 
            f[x][0] += max(f[fa[x]][0], f[fa[x]][1] + cost[x]); 
            f[x][1] = f[x][0] + max(mx[x][i], f[fa[x]][0] + cost[x] - max(f[fa[x]][0], f[fa[x]][1] + cost[x])); 
        } 
        ans = max(ans, f[son[x][i]][0] + max(f[x][0], f[x][1] + cost[son[x][i]])); 
        rdfs(son[x][i]); 
    } 
} 
int main () { 
#ifndef ONLINE_JUDGE 
    freopen("cpp.in", "r", stdin); 
#endif
    clearGraph(); 
    N = gi(); 
    for (int i = 1; i < N; i++) { 
        int u = gi(), v = gi(), w = gi(); 
        Add_Edge(u, v, w); 
        Add_Edge(v, u, w); 
    } 
    dfs(1);
    ans = f[1][0];
    rdfs(1); 
    printf("%d\n", ans); 
    return 0; 
} 

【LG3647】[APIO2014]连珠线

上一篇:C#编程总结(八)数字签名


下一篇:【WPF on .NET Core 3.0】 Stylet演示项目 - 简易图书管理系统(2)