G - Distance Queries on a Tree
涉及知识点
树链剖分,最近公共祖先
题意
给定N个点的无根带权树,给定N-1条边的信息为$u_i \leftrightarrow v_i$,权值为w_i,现在做Q次询问:
1 i w
: 表示把第i条边的权重改为w2 u v
: 询问从节点u到v的距离
($n \le 2e5, w_i, w \le 1e9, q \le 2e5$)
题解
我不会啊,我只会不修改的,麻了,等着看题解 [已更新]
应该时刻牢记,
$$dist(u, v) = dist(u, root) + dist(v, root) - 2dist(lca(u, v), root)$$
这里$lca(u, v)$表示u和v的最近公共祖先
其次这是一道树链剖分接近模板的题,首先处理一下所有边u->v,把权值记在深度更大的那个节点上。然后对这颗原始的无根带权树做树链剖分,可以在$O(log^2n)$的时间内询问任意两点之间的距离(把所有节点到树根的距离都变成了O(logn)段时间戳连续的区间,而求区间和又是O(logn)的时间复杂度,通过树状数组或者线段树这种可以维护区间和性质的数据结构)。
再看给定的两个操作,第一个操作就是单点修改(树链剖分路径修改的特殊情况),第二个操作利用上面给的公式即可。所以本题就是一个彻头彻尾的树剖板子题,然而我好久没写完全忘了这件事。总时间复杂度$O(nlog^2n+qlog^2n)$,代码如下。
/**
* @file template.cpp
* @author Emanual20(Emanual20@foxmail.com)
* @brief For Codeforces, Atcoder or some other OJs else
* @version 0.1
* @date 2023-3-22
*
* @copyright Copyright (c) 2022
*
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;
int n, root, q;
vector<int> edges[maxn];
struct item{
int nto, nw, nidx;
};
vector<item> ne[maxn];
int idx2dnode[maxn];
#define lson(x) ((x) << 1)
#define rson(x) ((x) << 1 | 1)
#define father(x) ((x) >> 1)
struct seg_node{
int left, right;
ll sum, lazy;
};
struct HeavyLightNode{
int fath, heavyson, top;
int sz, depth;
int w, seq;
} a[maxn];
struct HeavyLightDecomposition{
public:
int Timestamp, ts2orindex[maxn];
seg_node tree[4 * maxn];
public:
void init(){
Timestamp = 0, memset(ts2orindex, 0, sizeof(ts2orindex));
}
void dfs1(int now, int fm, int depth){
a[now].fath = fm, a[now].depth = depth, a[now].sz = 1;
for(auto &it : edges[now]){
if(it != fm){
dfs1(it, now, depth + 1);
a[now].sz += a[it].sz;
if(a[it].sz > a[a[now].heavyson].sz)
a[now].heavyson = it;
}
}
}
void dfs2(int now, int fm, int tp){
Timestamp += 1, a[now].seq = Timestamp, ts2orindex[Timestamp] = now, a[now].top = tp;
// if node now haven't any heavy sons, return
if(!a[now].heavyson) return;
dfs2(a[now].heavyson, now, tp);
for(auto &it : edges[now]){
if(it != fm && it != a[now].heavyson){
// light node is the first node of any chain
dfs2(it, now, it);
}
}
}
void Pushup(int k){
tree[k].sum = tree[lson(k)].sum + tree[rson(k)].sum;
}
void build_seg(int left, int right, int k = 1){
tree[k].left = left, tree[k].right = right;
if (left == right){
tree[k].sum = a[ts2orindex[left]].w;
return;
}
int mid = (left + right) >> 1;
build_seg(left, mid, lson(k));
build_seg(mid + 1, right, rson(k));
Pushup(k);
}
void Pushdown(int k){
if (tree[k].lazy == 0) return;
tree[lson(k)].lazy += tree[k].lazy, tree[rson(k)].lazy += tree[k].lazy;
tree[lson(k)].lazy %= MOD, tree[rson(k)].lazy %= MOD;
tree[lson(k)].sum += tree[k].lazy * (tree[lson(k)].right - tree[lson(k)].left + 1);
tree[lson(k)].sum %= MOD;
tree[rson(k)].sum += tree[k].lazy * (tree[rson(k)].right - tree[rson(k)].left + 1);
tree[rson(k)].sum %= MOD;
tree[k].lazy = 0;
}
void Update_seg(int l, int r, int x, int y, ll C, int k = 1){
if (x <= l && r <= y){
tree[k].sum = C, tree[k].sum %= MOD;
return;
}
Pushdown(k);
int mid = (l + r) >> 1;
if(x <= mid) Update_seg(l, mid, x, y, C, lson(k));
if(y > mid) Update_seg(mid + 1, r, x, y, C, rson(k));
Pushup(k);
}
ll Query_seg(int l, int r, int x, int y, int k = 1){
ll ret = 0;
if (x <= l && r <= y){
ret = tree[k].sum;
return ret;
}
Pushdown(k);
int mid = (l + r) >> 1;
if (mid >= x) ret += Query_seg(l, mid, x, y, lson(k));
if (mid < y) ret += Query_seg(mid + 1, r, x, y, rson(k));
return ret;
}
void UpdateSubtree(int u, ll k){
Update_seg(1, n, a[u].seq, a[u].seq + a[u].sz - 1, k);
}
ll QuerySubtree(int u){
return Query_seg(1, n, a[u].seq, a[u].seq + a[u].sz - 1);
}
void UpdatePath(int u, int v, ll k){
while(a[u].top != a[v].top){
if(a[a[u].top].depth < a[a[v].top].depth)
swap(u, v);
Update_seg(1, n, a[a[u].top].seq, a[u].seq, k);
u = a[u].top;
u = a[u].fath;
}
if(a[u].depth < a[v].depth)
swap(u, v);
Update_seg(1, n, a[v].seq, a[u].seq, k);
}
ll QueryPath(int u, int v){
ll ret = 0;
while(a[u].top != a[v].top){
if(a[a[u].top].depth < a[a[v].top].depth)
swap(u, v);
ret += Query_seg(1, n, a[a[u].top].seq, a[u].seq);
u = a[u].top;
u = a[u].fath;
}
if(a[u].depth < a[v].depth)
swap(u, v);
ret += Query_seg(1, n, a[v].seq, a[u].seq);
return ret;
}
ll QueryLCA(int u, int v){
while(a[u].top != a[v].top){
if(a[a[u].top].depth < a[a[v].top].depth)
swap(u, v);
u = a[a[u].top].fath;
}
return a[u].depth < a[v].depth ? u : v;
}
};
void dfs_init(int now, int fm){
for(auto &it : ne[now]){
auto nto = it.nto, nw = it.nw, nidx = it.nidx;
if(nto != fm){
a[nto].w = nw, idx2dnode[nidx] = nto;
dfs_init(nto, now);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i < n; i++){
int nfm, nto, nw;
cin >> nfm >> nto >> nw;
edges[nfm].push_back(nto), edges[nto].push_back(nfm);
ne[nfm].push_back({nto, nw, i}), ne[nto].push_back({nfm, nw, i});
}
root = 1;
dfs_init(1, -1);
HeavyLightDecomposition hld;
hld.init();
hld.dfs1(root, -1, 1);
hld.dfs2(root, -1, root);
hld.build_seg(1, n);
cin >> q;
while(q--){
int op;
cin >> op;
if(op == 1){
int nidx, nw;
cin >> nidx >> nw;
hld.UpdatePath(idx2dnode[nidx], idx2dnode[nidx], nw);
}
else if(op == 2){
int nu, nv;
cin >> nu >> nv;
auto res = hld.QueryPath(root, nu) + hld.QueryPath(root, nv) - 2 * hld.QueryPath(root, hld.QueryLCA(nu, nv));
cout << res << "\n";
}
}
return 0;
}