「IOI2008」Island

题目链接:洛谷P4381

Description

给定一个带权的基环树森林,求每棵基环树的最长简单路径之和。

Data Range

$2\leq N\leq 10^6,1\leq L_i\leq 10^8$

Solution

每棵基环树的最长简单路径我们就简称为基环树的直径
按照基环树的处理套路,我们首先将环找出来之后开始分类讨论。

第一种情况

基环树的直径不经过基环。
那么我们就从每一个环上的点开始查找不经过其他点的直径即可。

第二种情况

基环树的直径通过基环,那么显然我们需要维护基环上的点到它的子树内的最深深度,记为$d_i$。
这种情况的答案就是$max(d_i+d_j+dist(i,j))$。
因为$dist(i,j)$有顺时针和逆时针的方向,所以我们就限定这个方向,将基环序列扩大一倍后用单调队列维护一下即可。
我们记录从根节点顺时针或者逆时针转圈的距离,相同的节点会有两个距离,这个距离记为$a_i$。
那么对于一对$(i,j)$的答案就是$max(d_i+d_j+a_i-a_j)$,因为$i$是固定的,所以我们就只需要找到$max(d_j-a_j)$这个东西就用单调队列找。

Code

#include <bits/stdc++.h>
using namespace std;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void read(T& x) {
  x = 0; char ch = 0; int f = 1;
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  x *= f;
}
typedef long long ll;
const int N = 1e6 + 5;
struct _edge {
  int to, nt; ll w;
} E[N << 1];
int H[N], from[N], s[N], fa[N], q[N << 1];
ll a[N << 1], d[N];
ll diameter, ans;
int n, edgeCnt, m, root;
bool cir[N], vis[N];
bool isfind;
void addEdge(int u, int v, ll w) {
  E[++edgeCnt] = (_edge) {v, H[u], w};
  H[u] = edgeCnt;
}
void findCir(int u, int inEdge, int _fa) {
  vis[u] = 1; fa[u] = _fa;
  for (int e = H[u]; e; e = E[e].nt) {
    if (isfind) return;
    if (e == (inEdge ^ 1)) continue;
    int v = E[e].to;
    from[v] = e;
    if (vis[v]) {
      s[++m] = v; cir[v] = 1;
      int ver = u;
      while (ver != v) {
        cir[ver] = 1; s[++m] = ver;
        ver = fa[ver];
      }
      isfind = 1;
      return;
    } else findCir(v, e, u);
  }
}
void dfs1(int u, int fa, ll dist, int rt) {
  if (d[rt] < dist) d[rt] = dist, root = u;
  vis[u] = 1;
  for (int e = H[u]; e; e = E[e].nt) {
    int v = E[e].to;
    if ((cir[v] && v != rt) || v == fa) continue;
    dfs1(v, u, dist + E[e].w, rt);
  }
}
void dfs2(int u, int fa, ll dist, int rt) {
  chkmax(diameter, dist);
  vis[u] = 1;
  for (int e = H[u]; e; e = E[e].nt) {
    int v = E[e].to; 
    if ((cir[v] && v != rt) || v == fa) continue;
    dfs2(v, u, dist + E[e].w, rt);
  }
}
void solve(int u) {
  ll res = 0; m = 0; isfind = 0;
  findCir(u, 0, 0); 
  a[1] = 0;
  for (int i = 1; i <= m; i++) s[i + m] = s[i];
  for (int i = 2; i <= m * 2; i++) 
    a[i] = a[i - 1] + E[from[s[i - 1]]].w;
  for (int i = 1; i <= m; i++) {
    diameter = 0ll;
    dfs1(s[i], 0, 0ll, s[i]), dfs2(root, 0, 0ll, s[i]);
    chkmax(res, diameter);
  }
  int head = 1, tail = 1; q[1] = 1;
  for (int i = 2; i <= m * 2; i++) {
    while (head <= tail && i - q[head] >= m) head++;
    int j = q[head];
    chkmax(res, a[i] - a[j] + d[s[i]] + d[s[j]]);
    while (head <= tail && d[s[i]] - a[i] >= d[s[q[tail]]] - a[q[tail]]) tail--;
    q[++tail] = i;
  }
  ans += res;
}
int main() {
  read(n); edgeCnt = 1; ans = 0ll;
  for (int i = 1; i <= n; i++) {
    int v; ll w;
    read(v); read(w);
    addEdge(i, v, w), addEdge(v, i, w);
  }
  for (int i = 1; i <= n; i++) 
    if (!vis[i]) solve(i);
  printf("%lld\n", ans);
  return 0; 
}
最后修改:2019 年 10 月 03 日 10 : 42 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论