题目描述

题解

根据给出的连接方式，我们可以发现对于一条蓝线它的连接一定是从某节点开始向根节点方向一直到另一节点结束。

而且长度一定为偶数段（好像没什么用）。

如果只考虑以 \(1\) 为根 \(u\) 的子树的话，可以通过简单的动态规划解决。

设 \(dp_{i, 0/1}\) 为点 \(i\) 的子树下，\(i\) 是否作为蓝线中点的最大得分，有转移方程： - \(dp_{u, 0} = \sum\limits_{v\in son(u)}\max\{dp_{v, 0}, dp_{v, 1} + w_{uv}\}\) - \(dp_{u, 1} = dp_{u, 0} + \max\limits_{v\in son(u)}\{dp_{v, 0} + w_{uv} - \max\{dp_{v, 0}, dp_{v, 1} + w_{u, v}\}\}\)

然后再考虑子树外的贡献。

当一个节点变为根节点时，所要变化的是其原本父亲的 \(dp\) 值与自己的。

如果当前节点是其父亲孩子中的最大值，那么此时父亲就无法从其转移只能从原先次大的转移而来，所以要记录次大值。

对于当前节点，新增了从其父亲来的贡献。

所以写的时候就先处理出 \(dp\) 数组，然后记录下在这个过程中除掉某个孩子的值 \(f_{i, 0/1, j}\) 表示 \(i\) 的子树中除掉 \(j\) 这个孩子的值。

#include <algorithm>
#include <cstdio>
#include <vector>

const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;

int n;
struct Edge {
  int v, w, nxt;

  Edge() : v(0), w(0), nxt(0) {}
  Edge(int _v, int _w, int _nxt) : v(_v), w(_w), nxt(_nxt) {}
} e[N << 1];
int head[N], edge_cnt;

void AddEdge(int u, int v, int w) {
  e[++edge_cnt] = Edge(v, w, head[u]);
  head[u] = edge_cnt;
}

std::vector<int> f[N][2], maxn[N];
int dp[N][2];

void Dfs1(int u, int fa) {
  dp[u][0] = 0, dp[u][1] = -INF;
  int maxn1 = -INF, maxn2 = -INF;
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].v, w = e[i].w;
    if (v == fa)
      continue;
    Dfs1(v, u);
    dp[u][0] += std::max(dp[v][0], dp[v][1] + w);
    if (dp[v][0] + w - std::max(dp[v][0], dp[v][1] + w) > maxn1)
      maxn2 = maxn1, maxn1 = dp[v][0] + w - std::max(dp[v][0], dp[v][1] + w);
    else if (dp[v][0] + w - std::max(dp[v][0], dp[v][1] + w) > maxn2)
      maxn2 = dp[v][0] + w - std::max(dp[v][0], dp[v][1] + w);
  }
  dp[u][1] = dp[u][0] + maxn1;
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].v, w = e[i].w;
    if (v == fa)
      continue;
    f[u][0].push_back(dp[u][0] - std::max(dp[v][0], dp[v][1] + w));
    if (dp[v][0] + w - std::max(dp[v][0], dp[v][1] + w) == maxn1) {
      f[u][1].push_back(f[u][0].back() + maxn2);
      maxn[u].push_back(maxn2);
    } else {
      f[u][1].push_back(f[u][0].back() + maxn1);
      maxn[u].push_back(maxn1);
    }
  }
}

int ans;

void Dfs2(int u, int fa, int l) {
  for (int i = head[u], cnt = 0; i; i = e[i].nxt) {
    int v = e[i].v, w = e[i].w;
    if (v == fa)
      continue;
    dp[u][0] = f[u][0][cnt], dp[u][1] = f[u][1][cnt];
    if (fa) {
      dp[u][0] += std::max(dp[fa][0], dp[fa][1] + l);
      dp[u][1] = dp[u][0] +
                 std::max(maxn[u][cnt],
                          dp[fa][0] + l - std::max(dp[fa][0], dp[fa][1] + l));
    }
    ans = std::max(ans, dp[v][0] + std::max(dp[u][0], dp[u][1] + w));
    Dfs2(v, u, w);
    ++cnt;
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 2, u, v, w; i <= n; ++i) {
    scanf("%d%d%d", &u, &v, &w);
    AddEdge(u, v, w), AddEdge(v, u, w);
  }
  Dfs1(1, 0);
  // for (int i =1; i <= n; ++i)
  //   printf("> %d %d\n", dp[i][0], dp[i][1]);
  Dfs2(1, 0, 0);
  printf("%d\n", ans);
  return 0;
}

hello_world2005's blog

「APIO2014」连珠线题解

题目描述

题解