Qtree1

题面

思路:

很裸的一道树剖题,我们把边权化为点权就可以了。注意不要加上两点的LCA。当我们两个点跳到同一条链上时,深度更浅的点就是两点的LCA了。我们只需查询区间$[id[x]+1,id[y]]$就可以了。

代码:
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>
using namespace std;
const int maxn = 1e5 + 10;
#define int long long
int size[maxn],son[maxn],n,head[maxn],tot,top[maxn],fa[maxn],dep[maxn];
int cnt,id[maxn],a[maxn],val[maxn];
struct node
{
int maxx;
}tr[maxn << 2];
struct edge
{
int next,to,w;
}e[maxn << 1];
void add(int u,int v,int w)
{
e[++tot] = (edge){head[u],v,w};
head[u] = tot;
}
void dfs1(int x,int f)
{
dep[x] = dep[f] + 1;
size[x] = 1;fa[x] = f;
int maxson = -1;
for(int i = head[x] ; i ; i = e[i].next)
{
int v = e[i].to;
if(v == f)continue;
val[v] = e[i].w;
dfs1(v,x);
size[x] += size[v];
if(size[v] > maxson)son[x] = v,maxson = size[v];
}
}
void dfs2(int x,int topf)
{
top[x] = topf;id[x] = ++cnt;
a[cnt] = val[x];
if(!son[x])return;
dfs2(son[x],topf);
for(int i = head[x] ; i ; i = e[i].next)
{
int v = e[i].to;
if(v == fa[x] or v == son[x])continue;
dfs2(v,v);
}
}
void build(int root,int l,int r)
{
if(l == r){
tr[root].maxx = a[l];
return;
}
int mid = l + r >> 1;
build(root << 1,l,mid);
build(root << 1 | 1,mid + 1,r);
tr[root].maxx = max(tr[root << 1].maxx,tr[root << 1 | 1].maxx);
}
void change(int root,int l,int r,int x,int b)
{
if(l == x and r == x){
tr[root].maxx = b;
return;
}
int mid = l + r >> 1;
if(x <= mid)change(root << 1,l,mid,x,b);
if(x > mid)change(root << 1 | 1,mid + 1,r,x,b);
tr[root].maxx = max(tr[root << 1].maxx,tr[root << 1 | 1].maxx);
}
int query(int root,int l,int r,int L,int R)
{
int ans = 0;
if(l >= L and r <= R)return tr[root].maxx;
int mid = l + r >> 1;
if(L <= mid)ans = max(ans,query(root << 1,l,mid,L,R));
if(R > mid)ans = max(ans,query(root << 1 | 1,mid + 1,r,L,R));
return ans;
}
int road_ask(int x,int y)
{
int ans = 0;
while(top[x] != top[y])
{
if(dep[top[x]] < dep[top[y]])swap(x,y);
ans = max(ans,query(1,1,n,id[top[x]],id[x]));
x = fa[top[x]];
}
if(dep[x] > dep[y])swap(x,y);
ans = max(ans,query(1,1,n,id[x] + 1,id[y]));
return ans;
}
signed main()
{
cin >> n;
for(int i = 1,u,v,w ; i < n ; ++ i)
{
cin >> u >> v >> w;
add(u,v,w);add(v,u,w);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
string opt;
while(cin >> opt)
{
if(opt == "DONE")break;
int a,b,x;
cin >> a >> b;
if(opt == "CHANGE"){
int v = e[a * 2 - 1].to,u = e[a * 2].to;
if(dep[v] > dep[u])x = v;
else x = u;
change(1,1,n,id[x],b);
}
if(opt == "QUERY")
{
if(a == b){
cout << 0 << endl;
continue;
}
cout << road_ask(a,b) << endl;
}
}
return 0;
}