JZOJ5833 永恒

题目大意

给你一个树，每个节点上有有一个部落，以及部落的人数，要你求出每个节点的子树里面人数最多的部落是哪一个（人数相同部落编号最小的）。

思路

全网第一篇分治题解

考虑树的dfs序，然后分治处理，每层只处理跨过mid的区间，然后就完了。

时间复杂度\(O(nlogn)\)，但常数比树上启发式合并小。

Code

#include <cstdio>

#include <cstdlib>

#include <cstring>

#define Re register

#define ll long long

bool st;

const int N = 400000 + 5;

inline int read() {

  int ret = 0, f = 0; char ch;

  do {

    ch = getchar();

    if (ch == '-') f = 1;

  } while (ch < '0' || ch > '9');

  do {

    ret = (ret << 3) + (ret << 1) + ch - '0';

    ch = getchar();

  } while (ch <= '9' && ch >= '0');

  return f ? - ret : ret;

}

inline void hand_in() {

  freopen("endless.in", "r", stdin);

  freopen("endless.out", "w", stdout);

}

struct Graph {

  int to[N << 1], nxt[N << 1], head[N], cnt;

  inline void add(int x, int y) {

    ++cnt;

    to[cnt] = y, nxt[cnt] = head[x], head[x] = cnt;

  }

}G;

int n, m, a[N], b[N];

struct Node { int val, id; }ans[N];

int dfn[N], sz[N], tot, id[N];

inline void dfs(int u, int fa) {

  dfn[u] = ++ tot;

  id[tot] = u;

  sz[u] = 1;

  for (Re int i = G.head[u];i;i = G.nxt[i]) {

    int v = G.to[i];

    if (v == fa) continue;

    dfs(v, u);

    sz[u] += sz[v];

  }

}

int c[N], sta[N], top;

inline void cal(int l, int r) {

  if (l >= r) {

    if (sz[id[l]] == 1) ans[id[l]].id = a[id[l]], ans[id[l]].val = b[id[l]];

    return;

  }

  int mid = (l + r) >> 1;

  cal(l, mid), cal(mid + 1, r);

  top = 0;

  int mx = 0, ids, p = mid + 1;

  for (int i = mid;i >= l; --i) {

    int u = id[i];

    sta[++top] = a[u];

    c[a[u]] += b[u];

    if (c[a[u]] > mx || (c[a[u]] == mx && ids > a[u])) mx = c[a[u]], ids = a[u];

    int ed = i + sz[u] - 1;

    if (ed <= mid || ed > r) continue;

    while (p <= ed) {

      int v = id[p];

      c[a[v]] += b[v];

      sta[++top] = a[v];

      if (c[a[v]] > mx || (c[a[v]] == mx && ids > a[v])) mx = c[a[v]], ids = a[v];

      p ++;

    }

    ans[u].val = mx, ans[u].id = ids;

  }

  for (Re int i = 1;i <= top; ++i) c[sta[i]] = 0;

}

bool ed;

int main() {

  hand_in();

  n = read(), m = read();

  for (Re int i = 1, u, v;i < n; ++i) {

    u = read(), v = read();

    G.add(u, v), G.add(v, u);

  }

  for (Re int i = 1;i <= n; ++i) {

    a[i] = read(), b[i] = read();

  }

  dfs(1, 0), cal(1, n);

  for (int i = 1;i <= n; ++i) {

    printf("%d %d\n", ans[i].id, ans[i].val);

  }

  return 0;

}

巴特西

JZOJ5833 永恒

题目大意

思路

Code

最新文章

热门文章