P4556

发表于 分类于
[Vani有约会]雨天的尾巴 /【模板】线段树合并

[Vani有约会]雨天的尾巴 /【模板】线段树合并

只要别往树剖上想就好了（动态开点的话我觉得大概也是可以做的，就是稍微麻烦一点，而且复杂度两个 $\log$）。。。

显然这玩意树上差分就能解决了。。。

我们假设可以开一个二维数组 $val_{i,j}$ 表示第 $i$ 个点的 $j$ 型救济有多少。那么在这个数组上取最大值的位置就是这个点的答案。

但显然我们不太可能开这么多数组，那就动态开点线段树就完了。

正好还能解决最大值的问题。

那么树上差分应该就好做了，但是差分过后前缀和显然没有那么轻松了。

这里就要用线段树合并了，将子节点的线段树与父节点的线段树合并，然后给父节点。

线段树合并实际上不是层内直接同级合并（也没法合并），而是从最简单的叶子结点开始合并（只存了长度为 1 的区间，一般会很好合并），然后再一层一层 Pushup 上去，从而完成整个线段树的合并。

合并的过程是与线段树节点数线性相关的（好像很显然）。

我们动态开点一共要 $O(m\log n)$ 个点，所以最后线段树合并的复杂度也是 $O(m\log n)$ 的。

然后没了。

注意 Pushup，还有一个节点的值如果变成 0 了最大值编号要赋 0（因为这个时候就相当于没有了啊。。。）。。。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}

const ll N=1e5,M=2e7;

ll n,m,u,v,tot,cnt;
ll rt[N+5],fa[N+5],top[N+5],hs[N+5],siz[N+5],dt[N+5];
ll ver[N*2+5],head[N+5],nxt[N*2+5];

struct Sgt{
  ll ls,rs,ma,id;
  #define ls(x) tree[x].ls
  #define rs(x) tree[x].rs
  #define ma(x) tree[x].ma
  #define id(x) tree[x].id
}tree[M+5];

inline void Dfs(ll p,ll fath) {
  siz[p]=1;fa[p]=fath;dt[p]=dt[fath]+1;
  for(ll i=head[p];i;i=nxt[i]) {
    if(ver[i]==fath) continue;Dfs(ver[i],p);
    if(siz[ver[i]]>siz[hs[p]]) hs[p]=ver[i];
    siz[p]+=siz[ver[i]];
  }
}

inline void Dfs_(ll p,ll fath,ll topf) {
  top[p]=topf;if(hs[p]) Dfs_(hs[p],p,topf);
  for(ll i=head[p];i;i=nxt[i]) {
    if(ver[i]==fath||ver[i]==hs[p]) continue;
    Dfs_(ver[i],p,ver[i]);
  }
}

inline ll Getlca(ll x,ll y) {
  while(top[x]!=top[y]) {if(dt[top[x]]<dt[top[y]]) swap(x,y);x=fa[top[x]];}
  return dt[x]<dt[y]?x:y;
}

inline void Pushup(ll p) {
  if(ls(p)&&!rs(p)) {ma(p)=ma(ls(p));id(p)=id(ls(p));}
  else if(!ls(p)&&rs(p)) {ma(p)=ma(rs(p));id(p)=id(rs(p));}
  else if(ls(p)&&rs(p)) {
    if(ma(ls(p))>=ma(rs(p))) {ma(p)=ma(ls(p));id(p)=id(ls(p));}
    else {ma(p)=ma(rs(p));id(p)=id(rs(p));}
  }
}

inline void Add(ll p,ll lp,ll rp,ll x,ll k) {
  if(lp==rp) {
    ma(p)+=k;id(p)=lp;if(!ma(p)) id(p)=0;
    return;
  }
  ll mid=(lp+rp)>>1;
  if(x<=mid) {if(!ls(p)) {cnt++;ls(p)=cnt;}Add(ls(p),lp,mid,x,k);}
  if(x>mid) {if(!rs(p)) {cnt++;rs(p)=cnt;}Add(rs(p),mid+1,rp,x,k);}
  Pushup(p);
}

inline ll Merge(ll x,ll y,ll lp,ll rp) {
  if(!x||!y) {return x|y;}
  if(lp==rp) {ma(x)=ma(x)+ma(y);id(x)=lp;if(!ma(x)) id(x)=0;return x;}
  ll mid=(lp+rp)>>1;
  ls(x)=Merge(ls(x),ls(y),lp,mid);
  rs(x)=Merge(rs(x),rs(y),mid+1,rp);
  Pushup(x);return x;
}

inline void Solve(ll p,ll fath) {
  for(ll i=head[p];i;i=nxt[i]) {
    if(ver[i]==fath) continue;
    Solve(ver[i],p);rt[p]=Merge(rt[p],rt[ver[i]],0,N);
  }
}

inline void Addedge(ll u,ll v) {
  ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

int main() {

  n=read();m=read();
  for(ll i=1;i<n;i++) {
    u=read();v=read();Addedge(u,v);Addedge(v,u);
  }

  Dfs(1,0);Dfs_(1,0,1);

  for(ll i=1;i<=n;i++) {cnt++;rt[i]=cnt;}

  for(ll i=1;i<=m;i++) {
    ll x,y,z;x=read();y=read();z=read();
    Add(rt[x],0,N,z,1);Add(rt[y],0,N,z,1);
    ll w=Getlca(x,y);
    Add(rt[w],0,N,z,-1);if(fa[w]) Add(rt[fa[w]],0,N,z,-1);
  }

  Solve(1,0);

  for(ll i=1;i<=n;i++) {writeln(id(rt[i]));}

  return 0;
}