APIO2014 连线珠

题目:

  在达芬奇时代,有一个流行的儿童游戏称为连珠线。当然,这个游戏是关于珠子和线的。线是红色或蓝色的,珠子被编号为 1到 n。这个游戏从一个珠子开始,每次会用如下方式添加一个新的珠子:
  Append(w, v):一个新的珠子 w 和一个已经添加的珠子 v 用红线连接起来。
  Insert(w, u, v):一个新的珠子 w 插入到用红线连起来的两个珠子 u,v 之间。具体过程是删去 u,v 之间红线,分别用蓝线连接 u,w 和 w,v。
  每条线都有一个长度。游戏结束后,你的最终得分为蓝线长度之和。
  给你连珠线游戏结束后的游戏局面,只告诉了你珠子和链的连接方式以及每条线的长度,没有告诉你每条线分别是什么颜色。
  你需要写一个程序来找出最大可能得分。即,在所有以给出的最终局面结束的连珠线游戏中找出那个得分最大的,然后输出最大可能得分。

思路:

  模拟赛时理解错题意.....题目的操作要求是只能从一个珠子出发,所以那种每个点选两条边的使得边权和最大的模型是错误的....
  先枚举根作为初始的一颗珠子,如果要延伸红边就直接连一个儿子,如果要延伸蓝边就连一对父子。也就是说,所有的蓝边都是以 爷爷-父亲-儿子 的形式存在的。
  设 表示以 为根的子树中, 点与父亲的连边是否为蓝边的边权和(为了后面换根方便不包括向父亲的边)。
  设
  
  
  这样就得到了一个 的 dp,下一步优化就是去掉枚举根的过程,每次把以父亲为根的状态转到以当前为根的状态(这个应该已经遇到好几次了吧)。只要删去当前点对父亲的贡献,再把父亲加入当前点就行了(具体看实现?)。

代码:

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++)
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
const int N = 200005;

template<class T>
inline void rd(T &a) {
#define gc getchar()
    char c;
    bool f = false;
    for(c = gc; !isdigit(c); c = gc) f |= (c == '-');
    for(a = 0; isdigit(c); c = gc) a = (a << 1) + (a << 3) + c - '0';
    if(f) a = -a;
#undef gc
}

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k = G.HEAD[o]; k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void add(int x, T w) {NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w;}
    T& operator[] (int x) {return W[x];}
};
struct Edge {int to, w;};
Link<N, N * 2, Edge> G;

int dp1[N], dp2[N][2], id[N][2];
int sum[N];
void dfs1(int o, int f) {
    dp1[o] = sum[o] = 0;
    dp2[o][0] = dp2[o][1] = -1e9;
    erep(k, G, o) {
        int v = G[k].to;
        if(v == f) continue;
        dfs1(v, o);
        sum[o] += max(dp1[v], dp2[v][0] + G[k].w);
    }
    dp1[o] = sum[o];
    erep(k, G, o) {
        int v = G[k].to;
        if(v == f) continue;
        int val = max(dp1[v], dp2[v][0] + G[k].w);
        int now = dp1[v] - val + G[k].w + sum[o];
        if(tomax(dp2[o][1], now)) id[o][1] = v;
        if(dp2[o][0] < dp2[o][1]) {
            swap(id[o][0], id[o][1]);
            swap(dp2[o][0], dp2[o][1]);
        }
    }
}

void dfs2(int o, int f, int e) {
    if(o != 1) {
        int d = (id[f][0] == o);
        int val = max(dp1[o], dp2[o][0] + e);
        int tmp = max(dp1[f] - val, dp2[f][d] + e - val);
        dp1[o] += tmp;
        rep(i, 0, 1) dp2[o][i] += tmp;
        int now = dp1[f] - val + e + sum[o];
        if(tomax(dp2[o][1], now)) id[o][1] = f;
        if(dp2[o][0] < dp2[o][1]) {
            swap(dp2[o][0], dp2[o][1]);
            swap(id[o][0], id[o][1]);
        }
    }
    erep(k, G, o) {
        int v = G[k].to;
        if(v == f) continue;
        dfs2(v, o, G[k].w);
    }
}

int main() {
    File(beads);
    int n;
    rd(n);
    rep(i, 2, n) {
        int u, v, d;
        rd(u); rd(v); rd(d);
        G.add(u, (Edge) {v, d});
        G.add(v, (Edge) {u, d});
    }
    dfs1(1, 0); 
    dfs2(1, 0, 0);
    int ans = 0;
    rep(i, 1, n) tomax(ans, dp1[i]);
    printf("%d\n", ans);
    return 0;
}