过路费(树链剖分入门)

描述

传送门:FZU - 2082

有$n$座城市,由$n-1$条路相连通,使得任意两座城市之间可达。每条路有过路费,要交过路费才能通过。每条路的过路费经常会更新,现问你,当前情况下,从城市$a$到城市$b$最少要花多少过路费。

Input

有多组样例,每组样例第一行输入两个正整数$n,m$($2 ≤ n≤50000$,$1≤m ≤ 50000$),接下来$n-1$行,每行$3$个正整数$a$ $b$ $c$,($1 ≤ a,b ≤ n$ , $a ≠ b$ , $1 ≤ c ≤ 1000000000$).数据保证给的路使得任意两座城市互相可达。接下来输入$m$行,表示$m$个操作,操作有两种:

  • 一. 0 a b ,表示更新第$a$条路的过路费为$b$,$1 ≤ a ≤ n-1$ ;
  • 二. 1 a b ,表示询问$a$到$b$最少要花多少过路费。

Output

对于每个询问,输出一行,表示最少要花的过路费。

Sample Input

2 3
1 2 1
1 1 2
0 1 2
1 2 1

Sample Output

1
2

思路

  • 树链剖分的入门题。
  • 这题要处理的是边权,我们可以把边权转化为儿子结点的点权。所以在dfs后,深度较深的点的点权就是题中的边权。然后就裸上轻重链剖分,用线段树维护一下路径的点权之和就好。(因为树上的路径是唯一的)然后在查询的时候,也要稍微改一改~
  • 注意数据范围,用long long
  • PS:树状数组来维护也可以,而且会比较好写。

代码

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int maxn = 1 << 15;
struct HLD
{
int n, dfs_clock;
int sz[maxn], top[maxn], son[maxn], dep[maxn], fa[maxn], id[maxn], val[maxn];
vector<int> G[maxn];
vector<pair<PII, int> > edges;
void init(int n)
{
this->n = n, clr(son, -1), dfs_clock = 0;
edges.clear();
for (int i = 0; i <= n; i++) G[i].clear();
}
void add_edge(int u, int v, int w) { G[u].pb(v), G[v].pb(u), edges.pb(mp(mp(u, v), w)); }
void dfs(int u, int p, int d)
{
dep[u] = d, fa[u] = p, sz[u] = 1;
for (int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if (v == p) continue;
dfs(v, u, d + 1);
sz[u] += sz[v];
if (son[u] == -1 || sz[v] > sz[son[u]]) son[u] = v;
}
}
void link(int u, int t)
{
top[u] = t, id[u] = ++dfs_clock;
if (son[u] == -1) return;
link(son[u], t);
for (int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if (v != son[u] && v != fa[u]) link(v, v);
}
}
void getval()
{
clr(sumv, 0);
for (int i = 0; i < edges.size(); i++)
{
int &u = edges[i].X.X, &v = edges[i].X.Y;
int w = edges[i].Y;
if (dep[u] > dep[v]) swap(u, v);
update(id[v], w, 1, n);
}
}
void update_path(int p, int w)
{
int v = edges[p - 1].X.Y;
update(id[v], w, 1, n);
}
ll query_sum(int u, int v)
{
ll ret = 0;
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]]) swap(u, v);
ret += query_sum(id[top[u]], id[u], 1, n);
u = fa[top[u]];
}
if (u == v) return ret;
if (dep[u] > dep[v]) swap(u, v);
ret += query_sum(id[son[u]], id[v], 1, n);
return ret;
}
// Segment Tree
#define lson rt << 1
#define rson rt << 1 | 1
#define Lson l, m, lson
#define Rson m + 1, r, rson
ll sumv[maxn << 2];
inline void pushup(int rt) { sumv[rt] = sumv[lson] + sumv[rson]; }
void update(int p, int v, int l, int r, int rt = 1)
{
if (l == r)
{
sumv[rt] = v;
return;
}
int m = l + r >> 1;
if (p <= m)
update(p, v, Lson);
else
update(p, v, Rson);
pushup(rt);
}
ll query_sum(int L, int R, int l, int r, int rt = 1)
{
if (L <= l && r <= R) return sumv[rt];
int m = l + r >> 1;
ll ret = 0;
if (L <= m) ret += query_sum(L, R, Lson);
if (m < R) ret += query_sum(L, R, Rson);
return ret;
}
} T;

int main()
{
int n, m;
while (~scanf("%d%d", &n, &m))
{
T.init(n);
for (int i = 1; i < n; i++)
{
static int u, v, c;
scanf("%d%d%d", &u, &v, &c);
T.add_edge(u, v, c);
}
T.dfs(1, 0, 0);
T.link(1, 1);
T.getval();
while (m--)
{
static int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if (a == 0)
T.update_path(b, c);
else
printf("%lld\n", T.query_sum(b, c));
}
}
}
捐助作者