LuoguP4949
原题描述
这道题题目简短，题意清楚，给个好评
这个题目是给了一个环套树，有Q此询问，每一次询问是改变一个边的权值或求两点之间的最短路径，废话。
我们珂以先考虑假设这些操作池在一珂树上的。
这就很好做，用树剖套线段树就足以解决。
边权怎么搞？珂以把一个边的权值看成这条边所连接的节点深度更深的儿子的点权。
Spoj375是一个很好的这种类型的题目，但特别卡时限。
但是，题目中是环套树(黑题哪有那么简单？)。
所以，我们把环套树分成一珂树和另外一个多余的边。 这显然珂以用并茶几搞出来。
接着，每一次询问分俩块：
- 查询在树中的路径的长度
- 考虑经过多余的边，查询路径一个节点到多余的边的一个节点，再次查询路径另一个节点到多余的边的另一个节点，最后加起来，再加上多余边的权值（注意还要反过来加一次！！）
结束了么？结束了
最后放一下代码：
#include <stdio.h>
#include <string.h>
#define Maxn 100010
int n, q, eu, ev, ew, ed;
int b[Maxn], a[Maxn];
int fa[Maxn];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
inline bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
return (fa[x] = y) | 1;
}
struct Edge {
int to, next, weight;
} e[Maxn << 1];
int head[Maxn], _cnt;
inline void AddEdge(int u, int v, int w) {
e[_cnt] = (Edge) {v, head[u], w};
head[u] = _cnt ++;
}
int par[Maxn], dep[Maxn];
int sz[Maxn], son[Maxn];
int top[Maxn], ind[Maxn], indx;
void dfs1(int u, int parent, int depth) {
par[u] = parent, dep[u] = depth, sz[u] = 1;
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to;
if (v == parent) continue;
dfs1(v, u, depth + 1); sz[u] += sz[v];
if (sz[son[u]] < sz[v]) son[u] = v;
b[v] = e[i].weight;
}
}
void dfs2(int u, int topv) {
top[u] = topv, ind[u] = ++ indx, a[indx] = b[u];
if (son[u]) dfs2(son[u], topv);
for (int i = head[u]; ~i; i = e[i].next)
if (e[i].to != par[u] && e[i].to != son[u])
dfs2(e[i].to, e[i].to);
}
int bit[Maxn];
inline void modify(int x, int y) {
while (x <= n) bit[x] += y, x += x & -x;
}
inline int query(int x) {
int ans = 0;
while (x) ans += bit[x], x -= x & -x;
return ans;
}
inline int TreeSum(int x, int y) {
int ans = 0;
while (top[x] ^ top[y]) {
if (dep[top[x]] < dep[top[y]]) x ^= y ^= x ^= y;
ans += query(ind[x]) - query(ind[top[x]] - 1);
x = par[top[x]];
}
if (ind[x] > ind[y]) x ^= y ^= x ^= y;
ans += query(ind[y]) - query(ind[x]);
return ans;
}
inline void change(int x, int y)
{
int l1 = (x << 1) - 1, l2 = x - 1 << 1;
int a = e[l1].to, b = e[l2].to;
int v = dep[a] < dep[b] ? b : a;
int now = query(ind[v]) - query(ind[v] - 1);
modify(ind[v], y - now);
}
int main() {
memset(head, -1, sizeof head);
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; ++ i) fa[i] = i;
for (int i = 1; i <= n; ++ i) {
int u, v, w; scanf("%d %d %d", &u, &v, &w);
if (unite(u, v)) AddEdge(u, v, w), AddEdge(v, u, w);
else eu = u, ev = v, ew = w, ed = i, _cnt += 2;
}
dfs1(1, 0, 1);
dfs2(1, 1);
for (int i = 1; i <= n; ++ i)
modify(i, a[i]);
while (q --) {
int opt, x, y;
scanf("%d %d %d", &opt, &x, &y);
if (opt == 1) {
if (x == ed) ew = y;
else change(x, y);
}
else {
int ans = TreeSum(x, y);
int ans1 = TreeSum(x, eu) + TreeSum(y, ev) + ew;
int ans2 = TreeSum(x, ev) + TreeSum(y, eu) + ew;
printf("%d\n", ans < (ans1 < ans2 ? ans1 : ans2) ? ans : (ans1 < ans2 ? ans1 : ans2));
}
}
return 0;
}