Rainypaster @ 2024-07-23 12:51:18
rt，好久没打树剖了，样例过，测试全 T
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int dep[N], size[N], a[N], son[N], f[N], top[N], _, id[N], w[N];
vector<int> g[N];
struct Segment_Tree
{
struct node
{
int l, r, maxn;
}tr[N << 2];
void build(int u, int l, int r)
{
tr[u].l = l, tr[u].r = r;
if(l == r) {
tr[u].maxn = a[l];
return ;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
}
void update(int u, int l, int r, int k)
{
if(l <= tr[u].l && tr[u].r <= r)
{
tr[u].maxn = k;
return ;
}
int mid = (tr[u].l + tr[u].r) >> 1;
if(l <= mid) update(u << 1, l, r, k);
if(r > mid) update(u << 1 | 1, l, r, k);
tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
}
int query(int u, int l, int r)
{
if(l <= tr[u].l && tr[u].r <= r)
{
return tr[u].maxn;
}
int mid = (tr[u].l + tr[u].r) >> 1;
int res = 0;
if(l <= mid) res = max(res, query(u << 1, l, r));
if(r > mid) res = max(res, query(u << 1 | 1, l, r));
tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
return res;
}
}seg;
struct ShuPou
{
int query(int x, int y)
{
int ans = 0;
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[x]]) swap(x, y);
ans += seg.query(1, id[top[x]], id[x]);
x = f[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
ans += seg.query(1, id[x] + 1, id[y]);
return ans;
}
}sp;
void dfs1(int u, int fa, int deep)
{
dep[u] = deep;
f[u] = fa;
size[u] = 1;
int maxn = -1;
for(int i = 0;i < g[u].size();i ++ ){
int v = g[u][i];
if(v == fa) continue;
dfs1(v, u, deep + 1);
size[u] += size[v];
if(size[v] > maxn){
maxn = size[v];
son[u] = v;
}
}
}
void dfs2(int u, int topfa)
{
id[u] = ++_;
a[_] = w[u];
top[u] = topfa;
if(!son[u]) return ;
dfs2(son[u], topfa);
for(int i = 0;i < g[u].size();i ++ ){
int v = g[u][i];
if(v == f[u] || v == son[u]) continue;
dfs2(v, v);
}
}
int main()
{
int n; cin >> n;
for(int i = 1;i < n;i ++ ){
int u, v, wi; cin >> u >> v >> wi;
g[u].push_back(v), g[v].push_back(u);
w[v] = wi;
}
// cout << '-';
dfs1(1, 0, 1), dfs2(1, 1);
seg.build(1, 1, n);
// cout << sp.query(1, 3);
string str; cin >> str;
while(str != "DONE")
{
int a, b; cin >> a >> b;
if(str == "CHANGE"){
seg.update(1, id[a] + 1, id[a] + 1, b);
}
else cout << sp.query(a, b) << endl;
cin >> str;
}
return 0;
}by ┭┮﹏┭┮ @ 2024-07-23 13:05:51
这里的第
by ┭┮﹏┭┮ @ 2024-07-23 13:08:20
@Rainypaster
by Rainypaster @ 2024-07-23 14:40:09
@┭┮﹏┭┮ 好的好的，thx
by Rainypaster @ 2024-08-02 09:25:40
@┭┮﹏┭┮ 还是 T，这个和全T没关系吧
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int dep[N], size[N], a[N], son[N], f[N], top[N], _, id[N], w_[N];
struct node
{
int u, v, w;
} w[N];
vector<int> g[N];
struct Segment_Tree
{
struct node
{
int l, r, maxn;
}tr[N << 2];
void build(int u, int l, int r)
{
tr[u].l = l, tr[u].r = r;
if(l == r) {
tr[u].maxn = a[l];
return ;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
}
void update(int u, int l, int r, int k)
{
if(l <= tr[u].l && tr[u].r <= r)
{
tr[u].maxn = k;
return ;
}
int mid = (tr[u].l + tr[u].r) >> 1;
if(l <= mid) update(u << 1, l, r, k);
if(r > mid) update(u << 1 | 1, l, r, k);
tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
}
int query(int u, int l, int r)
{
if(l <= tr[u].l && tr[u].r <= r)
{
return tr[u].maxn;
}
int mid = (tr[u].l + tr[u].r) >> 1;
int res = 0;
if(l <= mid) res = max(res, query(u << 1, l, r));
if(r > mid) res = max(res, query(u << 1 | 1, l, r));
tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
return res;
}
}seg;
struct ShuPou
{
int query(int x, int y)
{
int ans = 0;
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[x]]) swap(x, y);
ans += seg.query(1, id[top[x]], id[x]);
x = f[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
ans += seg.query(1, id[x] + 1, id[y]);
return ans;
}
}sp;
void dfs1(int u, int fa, int deep)
{
dep[u] = deep;
f[u] = fa;
size[u] = 1;
int maxn = -1;
for(int i = 0;i < g[u].size();i ++ ){
int v = g[u][i];
if(v == fa) continue;
dfs1(v, u, deep + 1);
size[u] += size[v];
if(size[v] > maxn){
maxn = size[v];
son[u] = v;
}
}
}
void dfs2(int u, int topfa)
{
id[u] = ++_;
a[_] = w_[u];
top[u] = topfa;
if(!son[u]) return ;
dfs2(son[u], topfa);
for(int i = 0;i < g[u].size();i ++ ){
int v = g[u][i];
if(v == f[u] || v == son[u]) continue;
dfs2(v, v);
}
}
int main()
{
int n; cin >> n;
for(int i = 1;i < n;i ++ ){
int u, v, wi; cin >> u >> v >> wi;
g[u].push_back(v), g[v].push_back(u);
w[i] = {u, v, wi};
w_[v] = wi;
}
// cout << '-';
dfs1(1, 0, 1), dfs2(1, 1);
seg.build(1, 1, n);
// cout << sp.query(1, 3);
string str; cin >> str;
while(str != "DONE")
{
int a, b; cin >> a >> b;
if(str == "CHANGE"){
seg.update(1, id[w[a].u] + 1, id[w[a].u] + 1, b);
}
else {
if(a == b) cout << 0 << endl;
else cout << sp.query(a, b) << endl;
}
cin >> str;
}
return 0;
}by ┭┮﹏┭┮ @ 2024-08-02 12:08:28
@Rainypaster 给你调了一下，还有一个问题是边权转点权的时候要将边放到边两节点深的那个。
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N = 1e5 + 5;
int dep[N], size[N], a[N], son[N], f[N], top[N], _, id[N], w_[N];
int rnk[N];
struct node
{
int u, v, w;
} w[N];
vector<pii> g[N];
struct Segment_Tree
{
struct node
{
int l, r, maxn;
}tr[N << 2];
void build(int u, int l, int r)
{
tr[u].l = l, tr[u].r = r;
if(l == r) {
tr[u].maxn = a[rnk[l]];
return ;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
}
void update(int u, int l, int r, int k)
{
if(l <= tr[u].l && tr[u].r <= r)
{
tr[u].maxn = k;
return ;
}
int mid = (tr[u].l + tr[u].r) >> 1;
if(l <= mid) update(u << 1, l, r, k);
if(r > mid) update(u << 1 | 1, l, r, k);
tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
}
int query(int u, int l, int r)
{
if(l <= tr[u].l && tr[u].r <= r)
{
return tr[u].maxn;
}
int mid = (tr[u].l + tr[u].r) >> 1;
int res = 0;
if(l <= mid) res = max(res, query(u << 1, l, r));
if(r > mid) res = max(res, query(u << 1 | 1, l, r));
tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
return res;
}
}seg;
struct ShuPou
{
int ans;
int query(int x, int y)
{
ans = 0;
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]]) swap(x, y);
//T 的原因是因为 y 打成了 x (
ans = max(ans,seg.query(1, id[top[x]], id[x]));
x = f[top[x]];
}
if(x == y)return ans;
if(dep[x] > dep[y]) swap(x, y);
ans = max(ans,seg.query(1, id[x] + 1, id[y]));
return ans;
}
}sp;
void dfs1(int u, int fa, int deep)
{
dep[u] = deep;
f[u] = fa;
size[u] = 1;
int maxn = -1;
for(int i = 0;i < g[u].size();i ++ ){
int v = g[u][i].first;
if(v == fa) continue;
dfs1(v, u, deep + 1);
size[u] += size[v],a[v] = g[u][i].second;
if(size[v] > maxn){
maxn = size[v];
son[u] = v;
}
}
}
void dfs2(int u, int topfa)
{
id[u] = ++_;rnk[_] = u;
top[u] = topfa;
if(!son[u]) return ;
dfs2(son[u], topfa);
for(int i = 0;i < g[u].size();i ++ ){
int v = g[u][i].first;
if(v == f[u] || v == son[u]) continue;
dfs2(v, v);
}
}
int main()
{
int n; cin >> n;
for(int i = 1;i < n;i ++ ){
int u, v, wi; cin >> u >> v >> wi;
g[u].push_back(mp(v,wi)), g[v].push_back(mp(u,wi));
w[i] = {u, v, wi};
// w_[v] = wi;
}
// cout << '-';
dfs1(1, 1, 1), dfs2(1, 1);
seg.build(1, 1, n);
// cout << sp.query(1, 3);
string str; cin >> str;
while(str != "DONE")
{
int a, b; cin >> a >> b;
if(str == "CHANGE"){
a = dep[w[a].u] > dep[w[a].v] ? w[a].u : w[a].v;
seg.update(1, id[a], id[a], b);
}
else {
if(a == b) cout << 0 << endl;
else cout << sp.query(a, b) << endl;
}
cin >> str;
}
return 0;
}