HDU 5029. Relief grain

发表于 分类于

链接

http://acm.hdu.edu.cn/showproblem.php?pid=5029

题意

每次分配给树上一条路径上所有点一个权值 $w$，求每个点拥有数量最多的权值是多少？

思路

树链剖分后，求 LCA 跳链时记录树上每个点的差分操作。

对于 DFS 序区间 $[l,r]$ 需要分配一个权值 $w$：

  • 对于 $l$，记录一下给 权值 $w$ 数量 $+1$；
  • 对于 $r+1$，记录一下给 权值 $w$ 数量 $-1$。

按照 DFS 序将每个点的差分操作更新到权值线段树，每个点更新完记录一下答案。

代码

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
121
122
123
124
125
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
// head
const int N=1e5+5;
int cnt,fa[N],dep[N],sz[N],top[N],son[N],dfn[N],id[N],res[N];
int ls[N<<2],rs[N<<2],tot[N<<2],mx[N<<2];
VI g[N];
VPII o[N];
void init(int n) {
    for(int i=1;i<=n;i++) {
        son[i]=0;
        g[i].clear();
        o[i].clear();
    }
    cnt=0;
}
void build(int p,int l,int r) {
    ls[p]=l,rs[p]=r;
    if(l==r) {
        tot[p]=0;
        mx[p]=l;
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    tot[p]=0;
    mx[p]=mx[p<<1];
}
void update(int p,int x,int v) {
    if(ls[p]==rs[p]) {tot[p]+=v;return;}
    int mid=ls[p]+rs[p]>>1;
    if(x<=mid) update(p<<1,x,v);
    else update(p<<1|1,x,v);
    if(tot[p<<1]>=tot[p<<1|1]) {
        tot[p]=tot[p<<1];
        mx[p]=mx[p<<1];
    }
    else {
        tot[p]=tot[p<<1|1];
        mx[p]=mx[p<<1|1];
    }
}
void dfs1(int u) {
    sz[u]=1;
    dep[u]=dep[fa[u]]+1;
    for(auto v:g[u]) if(v!=fa[u]) {
        fa[v]=u;
        dfs1(v);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int t) {
    top[u]=t;
    dfn[u]=++cnt;
    id[cnt]=u;
    if(son[u]) dfs2(son[u],t);
    for(auto v:g[u]) if(v!=fa[u]&&v!=son[u]) {
        dfs2(v,v);
    }
}
void solve(int a,int b,int c) {
    while(top[a]!=top[b]) {
        if(dep[top[a]]>dep[top[b]]) {
            o[dfn[top[a]]].EB(c,1);
            o[dfn[a]+1].EB(c,-1);
            a=fa[top[a]];
        }
        else {
            o[dfn[top[b]]].EB(c,1);
            o[dfn[b]+1].EB(c,-1);
            b=fa[top[b]];
        }
    }
    if(dep[a]>dep[b]) {
        o[dfn[b]].EB(c,1);
        o[dfn[a]+1].EB(c,-1);
    }
    else {
        o[dfn[a]].EB(c,1);
        o[dfn[b]+1].EB(c,-1);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    while(cin>>n>>m) {
        if(!n&&!m) break;
        init(n);
        for(int i=1;i<n;i++) {
            int u,v;cin>>u>>v;
            g[u].PB(v);
            g[v].PB(u);
        }
        dfs1(1);
        dfs2(1,1);
        build(1,0,100000);
        for(int i=1;i<=m;i++) {
            int x,y,z;cin>>x>>y>>z;
            solve(x,y,z);
        }
        for(int i=1;i<=n;i++) {
            for(auto x:o[i]) update(1,x.FI,x.SE);
            res[id[i]]=mx[1];
        }
        for(int i=1;i<=n;i++) cout<<res[i]<<'\n';
    }
    return 0;
}