[Luogu4556]雨天的尾巴

Posted on | In

这题给我的第一感觉就是树链剖分$+$树上差分，然而我不会

事实上主流做法确实是树链剖分，复杂度$O$$($$n$$logn^2$$)$

然而这题还可以线段树合并，复杂度$O$$($$n$$logn$$)$

但是跑得比树链剖分慢一倍，别问我为什么常数那么大

直接对每一个节点都维护一颗权值线段树

再套一个树上差分，最后直接线段树合并

因为这题空间卡得紧，所以离线操作

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
#include<bits/stdc++.h>
using namespace std;
const int M=100001;
const int N=8000008;
int w,cnt,num,d[N],l[N],r[N],t[N],to[M<<1],from[M<<1];
int X[M],Y[M],Z[M],fa[M],ans[M],son[M],sum[M],top[M],deep[M],head[M],root[M];
inline void add(int u,int v) {
    from[++num]=head[u];
    to[num]=v;
    head[u]=num;
}
inline int read() {
    char ch=getchar(); int c=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) c=(c<<3)+(c<<1)+(ch^'0'),ch=getchar();
    return c;
}
inline void update(int x) {
    if(d[l[x]]>=d[r[x]]) d[x]=d[l[x]],t[x]=t[l[x]];
    else d[x]=d[r[x]],t[x]=t[r[x]];
}
inline int merge(int a,int b,int x,int y) {
    if(!a) return b; if(!b) return a;
    if(x==y) { d[a]+=d[b]; t[a]=x; return a; }
    int mid=(x+y)>>1;
    l[a]=merge(l[a],l[b],x,mid),r[a]=merge(r[a],r[b],mid+1,y);
    update(a); return a;
}
inline void Dfs1(int x) {
    sum[x]=1; int maxx=-1;
    for(register int i=head[x];i;i=from[i])
        if(!deep[to[i]]) {
            deep[to[i]]=deep[x]+1,fa[to[i]]=x;
            Dfs1(to[i]); sum[x]+=sum[to[i]];
            if(sum[to[i]]>maxx) maxx=sum[to[i]],son[x]=to[i];
        }
}
inline void Dfs2(int x,int topx) {
    top[x]=topx; if(!son[x]) return ; Dfs2(son[x],topx);
    for(register int i=head[x];i;i=from[i]) if(!top[to[i]]) Dfs2(to[i],to[i]);
}
inline int LCA(int x,int y) {
    while(top[x]!=top[y]) {
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    return deep[x]<deep[y]?x:y;
}
inline int Change(int a,int x,int y,int pos,int val) {
    if(!a) a=++cnt;
    if(x==y) { d[a]+=val; t[a]=x; return a; }
    int mid=(x+y)>>1;
    if(pos<=mid) l[a]=Change(l[a],x,mid,pos,val);
    else r[a]=Change(r[a],mid+1,y,pos,val);
    update(a); return a;
}
inline void ReDfs(int x) {
    for(register int i=head[x];i;i=from[i])
        if(deep[to[i]]>deep[x]) ReDfs(to[i]),root[x]=merge(root[x],root[to[i]],1,w);
    if(d[root[x]]) ans[x]+=t[root[x]];
}
int main() {
    int n=read(),m=read(),x,y,z;
    for(register int i=1;i<n;++i) x=read(),y=read(),add(x,y),add(y,x);
    deep[1]=1; Dfs1(1),Dfs2(1,1);
    for(register int i=1;i<=m;++i) X[i]=read(),Y[i]=read(),Z[i]=read(),w=max(w,Z[i]);
    for(register int i=1;i<=m;++i) {
        int lca=LCA(X[i],Y[i]);
        root[X[i]]=Change(root[X[i]],1,w,Z[i],1),root[Y[i]]=Change(root[Y[i]],1,w,Z[i],1);
        root[lca]=Change(root[lca],1,w,Z[i],-1);
        if(fa[lca]) root[fa[lca]]=Change(root[fa[lca]],1,w,Z[i],-1);
    }
    ReDfs(1);
    for(register int i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}