线段树合并

· · 算法·理论

是的孩子们我复活了，虽然很快又要死了。

线段树合并指的是可以把两个大小相同的线段树合并在一起。区别于启发式合并，线段树合并 n 棵树的时间复杂度为 O(n\log n)。

模板

对于这个题目，一个很显然的思路是对于每一个点维护一个权值线段树，用差分和 LCA 把区间修改转化为单点修改。具体而言就是把 [1,x],[1,y] 两个添加后减去 [1,lca(x,y)],[1,fa[lca(x.y)]，其中 fa(x) 指的是 x 的直接父亲。

然后由于差分我们需要全局对于某个节点 x 的影响，容易发现对于子节点 y 上的差分值都会影响到 x，而上面的数据可以直接累加到 x 上，故使用线段树合并把 y 上的节点复制到 x 上去。

#include <bits/stdc++.h>
using namespace std;

inline int Read() {
  int x = 0,f = 1;
  char c = getchar();
  for(;c < '0' || c > '9';c = getchar()) f ^= (c == '-');
  for(;c >= '0' && c <= '9';c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
  return f ? x : -x;
}

const int _ = 1e5 + 5,__ = 5e6 + 5; 

struct Edge { int v,nxt; } e[_*2];
int head[_],ecnt;
void Add(int u,int v) { e[++ecnt] = Edge{v,head[u]}; head[u] = ecnt; }

int dep[_],fa[_][30],lg[_]; //LCA
void DFS(int x,int f) {
 fa[x][0] = f;
  dep[x] = dep[f] + 1;
  for(int i = 1;i <= lg[dep[x]] + 1;i++) {
    fa[x][i] = fa[fa[x][i - 1]][i - 1];
  }
  for(int i = head[x];i;i = e[i].nxt) {
    int y = e[i].v;
    if(y != f) DFS(y,x);
  }
}
int LCA(int x,int y) {
  if(dep[x] > dep[y]) swap(x,y);
  while(dep[x] < dep[y]) {
    y = fa[y][lg[dep[y] - dep[x]]];
  }
  if(x == y) return x;
  for(int i = lg[dep[x]];i >= 0;i--) {
    if(fa[x][i] != fa[y][i]) {
      x = fa[x][i];
      y = fa[y][i];
    }
  }
  return fa[x][0];
}
void Build(int n,int s) {
  for(int i = 2;i <= n;i++) lg[i] = lg[i / 2] + 1;
  DFS(s,0);
}

int n,m,cnt;
int rt[_],ans[_],sum[__],res[__],ls[__],rs[__];

void Update(int x) {  //处理最大值是哪个颜色
  if(sum[ls[x]] < sum[rs[x]]) res[x] = res[rs[x]],sum[x] = sum[rs[x]];
  else res[x] = res[ls[x]],sum[x] = sum[ls[x]];
}

int Merge(int a,int b,int x,int y) { //合并
  if(!a) return b;
  if(!b) return a;
  if(x == y) {
    sum[a] += sum[b];
    return a;
  }
  int mid = (x + y) / 2;
  ls[a] = Merge(ls[a],ls[b],x,mid);
  rs[a] = Merge(rs[a],rs[b],mid + 1,y);
  Update(a);
  return a;
}

void AddColor(int &id,int x,int y,int c,int v) { //添加颜色
  if(!id) id = ++cnt;
  if(x == y) {
    sum[id] += v,res[id] = c;
    return;
  }
  int mid = (x + y) / 2;
  if(c <= mid) AddColor(ls[id],x,mid,c,v);
  else AddColor(rs[id],mid + 1,y,c,v);
  Update(id);
}

void Cal(int x) {
  for(int i = head[x];i;i = e[i].nxt) {
    int y = e[i].v;
    if(y == fa[x][0]) continue;
    Cal(y);
    rt[x] = Merge(rt[x],rt[y],1,100000); //合并
  }
  ans[x] = res[rt[x]];
  if(sum[rt[x]] == 0) ans[x] = 0;
}

int main() {
  n = Read(),m = Read();
  for(int i = 1;i < n;i++) {
    int u = Read(),v = Read();
    Add(u,v),Add(v,u);
  }
  Build(n,1);
  for(int i = 1;i <= m;i++) {
    int x = Read(),y = Read(),z = Read(),lca = LCA(x,y);
    AddColor(rt[x],1,100000,z,1),AddColor(rt[y],1,100000,z,1);
    AddColor(rt[lca],1,100000,z,-1),AddColor(rt[fa[lca][0]],1,100000,z,-1); //差分
  }
  Cal(1);
  for(int i = 1;i <= n;i++) cout << ans[i] << '\n';
  return 0;
}