题意:求每个节点子树中出现最多颜色的编号和

树上启发式合并可以解决一些无修改的子树询问

先处理轻儿子,后处理重儿子,如果该节点是轻儿子,然后重新统计轻儿子的贡献,更新该节点的答案,如果该节点是轻儿子,那么将该节点的贡献删除,回溯

由于轻重链剖分一个点到根节点至多有$O(logn)$条轻边的性质,所以每个节点最多被重复遍历$O(logn)$次,总复杂度$O(nlogn)$
(是不是觉得很不对,我也这么觉得((((((

int cnt[MAXN], son[MAXN], siz[MAXN], head[MAXN], c[MAXN], n, m;
bool vis[MAXN];

struct Edge {
  int v, next;
}G[MAXN<<1];
inline void add(int u, int v) {
  static int tot = 0;
  G[++tot] = (Edge) {v, head[u]}; head[u] = tot;
}
ll cur, ans[MAXN];
int Max;
inline void dfs(int u, int fa) {
  siz[u] = 1;
  for(int i = head[u]; i; i = G[i].next) {
    int v = G[i].v;
    if (v == fa) continue;
    dfs(v, u); siz[u] += siz[v];
    if (siz[v] >= siz[son[u]]) son[u] = v;
  }
}

inline void update(int u, int fa, int V) {
  cnt[c[u]] += V;
  if (cnt[c[u]] > Max) Max = cnt[c[u]], cur = c[u];
  else if (cnt[c[u]] == Max) cur += c[u];
  for(int i = head[u]; i; i = G[i].next) {
    int v = G[i].v;
    if (v == fa || vis[v]) continue;
    update(v, u, V);
  }
}

inline void solve(int u, int fa, bool is) {
  for(int i = head[u]; i; i = G[i].next) {
    int v = G[i].v;
    if (v == fa || v == son[u]) continue;
    solve(v, u, 0);
  }
  if (son[u]) solve(son[u], u, 1), vis[son[u]] = 1;
  update(u, fa, 1);
  ans[u] = cur;
  vis[son[u]] = 0;
  if (!is) {
    update(u, fa, -1);
    Max = cur = 0;
  }
}

int main() {
#ifdef LOCAL_DEBUG
  // freopen("data.in", "r", stdin), freopen("data.out", "w", stdout);
  Dbg = 1; uint tim1 = clock();
#endif
  in, n;
  lop(i,1,n) in, c[i];
  lop(i,1,n-1) { 
    int u, v; in, u, v; add(u, v), add(v, u);
  }
  dfs(1, 0);
  solve(1, 0, 1);
  lop(i,1,n) out, ans[i], ' ';
#ifdef LOCAL_DEBUG
  fprintf(stderr, "\ntime:%.5lfms", (clock() - tim1) / (1.0 * CLOCKS_PER_SEC) * 1000);
#endif
  return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注