改了一个地方,现在 75pts:
为什么边权转点权时在递归子树后转是对的?
![](https://cdn.luogu.com.cn/upload/image_hosting/hnkfzx3x.png)
```cpp
#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define F(i,a,b) for(rll i=a;i<=b;i++)
#define Fdn(i,a,b) for(rll i=a;i>=b;i--)
#define pii pair<int, int>
using namespace std;
const int inf = 0x3f3f3f3f,mod = 1e9 + 7;
const int maxn = 1e4 + 7, maxm = 5e4 + 7;
int n, m;
struct edge {
int u, v, w;
bool operator < (const edge &x) const {
return w > x.w;
}
}Edge[maxm];
int MergeSiz[maxn], MergeFa[maxn];
int tot, head[maxn];
struct _edge_ {
int nxt, to, w;
}G[maxm << 1];
inline void AddEdge(int u, int v, int w) { G[++tot].nxt = head[u], G[tot].to = v, G[tot].w = w, head[u] = tot; }
int val[maxn];
int top[maxn], dfn[maxn], siz[maxn], hson[maxn], dep[maxn], rnk[maxn], fa[maxn], dfn_clock;
int MinNum[maxn << 2];
inline int GetFa(int x) { return ((x == MergeFa[x]) ? x : MergeFa[x] = GetFa(MergeFa[x])); }
inline void dfs1(int u, int f) {
siz[u] = 1, fa[u] = f, dep[u] = dep[f] + 1, hson[u] = -1;
for(int i = head[u]; i; i = G[i].nxt) {
int v = G[i].to;
if(v == f) continue ;
dfs1(v, u);
siz[u] += siz[v]; val[v] = G[i].w;
if(hson[u] == -1 || siz[hson[u]] < siz[v]) hson[u] = v;
}
}
inline void dfs2(int u, int tp) {
dfn[u] = ++dfn_clock, rnk[dfn_clock] = u, top[u] = tp;
if(hson[u] != -1) dfs2(hson[u], tp);
for(int i = head[u]; i; i = G[i].nxt) {
int v = G[i].to;
if(v != fa[u] && v != hson[u])
dfs2(v, v);
}
}
inline void PushUp(int p) { MinNum[p] = min(MinNum[p << 1], MinNum[p << 1 | 1]); }
inline void Build(int p, int l, int r) {
if(l == r)
return MinNum[p] = val[rnk[l]], void();
int mid = (l + r) >> 1;
Build(p << 1, l, mid), Build(p << 1 | 1, mid + 1, r);
PushUp(p);
}
inline int Query(int p, int l, int r, int s, int t) {
if(s > t) return inf;
if(s <= l && r <= t)
return MinNum[p];
int mid = (l + r) >> 1, ret = inf;
if(s <= mid) ret = min(ret, Query(p << 1, l, mid, s, t));
if(mid < t) ret = min(ret, Query(p << 1 | 1, mid + 1, r, s, t));
return ret;
}
inline int QueryPath(int x, int y) {
int ret = inf;
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y); //cout << dfn[top[x]] << " " << dfn[x] << '\n';
ret = min(ret, Query(1, 1, n, dfn[top[x]], dfn[x]));
x = fa[top[x]];
}
if(x == y) return ret;
if(dep[x] > dep[y]) swap(x, y); //cout << dfn[x] + 1 << " " << dfn[y] << "yyy\n";
ret = min(ret, Query(1, 1, n, dfn[x] + 1, dfn[y]));
return ret;
}
int _;
bool vis[maxn];
int R[maxn], _tot;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
memset(val, 0x3f, sizeof val);
cin >> n >> m;
F(i, 1, m)
cin >> Edge[i].u >> Edge[i].v >> Edge[i].w;
sort(Edge + 1, Edge + 1 + m);
F(i, 1, n) MergeFa[i] = i, MergeSiz[i] = 1;
F(i, 1, m) {
int u = Edge[i].u, v = Edge[i].v, w = Edge[i].w,
x = GetFa(u), y = GetFa(v);
if(x == y) continue;
if(MergeSiz[x] < MergeSiz[y]) swap(x, y);
//cout << x << " " << y << " " << u << " " << v << " " << w << "ikura!\n";
MergeFa[y] = x, MergeSiz[x] += MergeSiz[y];
AddEdge(u, v, w), AddEdge(v, u, w);
}
F(i, 1, n) {
if(!vis[MergeFa[i]]) {
vis[MergeFa[i]] = 1;
dfs1(MergeFa[i], 0), dfs2(MergeFa[i], MergeFa[i]);
}
}
//F(i, 1, n) cout << dfn[i] << ' ' ;
//cout << "yousa!\n";
//F(i, 1, n) cout << fa[i] << ' ' << val[i] << '\n';
//cout << "Furina!\n";
Build(1, 1, n);
cin >> _;
while(_--) {
int u, v; cin >> u >> v;
if(GetFa(u) != GetFa(v)) {
cout << "-1\n";
continue ;
}
cout << QueryPath(u, v) << '\n';
}
return 0;
}
```
by Snowy_Fujisaki @ 2024-02-16 11:10:42
@[Snowy_Fujisaki](/user/759710) 你在 dfs1() 中没有标 vis
"为什么边权转点权时在递归子树后转是对的?"如果你回到了父亲节点,那就赋错了
by JT_dw_ @ 2024-02-16 11:22:25
@[Snowy_Fujisaki](/user/759710) 你的第一份代码里面,先转点权,然后判的父节点,这导致父节点的点权被修改
by Iniaugoty @ 2024-02-16 11:29:58
@[JT_dw_](/user/776600) @[gty314159](/user/768612) thx,改了判森林的,现在过了,此帖结。
by Snowy_Fujisaki @ 2024-02-16 11:33:41
同道中人
by WAI_kycm @ 2024-02-22 16:33:09