我感觉不会,所以求各位大佬分析一下我的代码:
#include<bits/stdc++.h>
#define endl '\n'
#define rep(i, s, e) for(int i = s, i##E = e; i <= i##E; ++i)
#define per(i, s, e) for(int i = s, i##E = e; i >= i##E; --i)
#define F first
#define S second
#define gmin(x, y) (x = min(x, y))
#define gmax(x, y) (x = max(x, y))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double f128;
typedef pair<int, int> pii;
template<class T = int> const T& read() {
static T x; cin >> x; return x;
}
constexpr int N = 2e5 + 5, K = 1e6 + 5, inf = 0x3f3f3f3f;
int n, k, ans = inf;
vector<pii> to[N];
int sz[N], mx[N], rt;
bitset<N> vis;
int buc[K];
vector<int> modi;
void getrt(int u, int f, int tot) {
sz[u] = 1;
mx[u] = 0;
for(auto i : to[u]) {
int v = i.F, w = i.S;
if(!vis[v] && v != f) {
getrt(v, u, tot);
sz[u] += sz[v];
gmax(mx[u], sz[v]);
}
}
gmax(mx[u], tot - sz[u] - 1);
if(mx[u] < mx[rt]) rt = u;
}
void dfs1(int u, int f, int s, int dep) {
if(s > k) return;
gmin(ans, dep + buc[k - s]);
for(auto i : to[u]) {
int v = i.F, w = i.S;
if(!vis[v] && v != f)
dfs1(v, u, s + w, dep + 1);
}
}
void dfs2(int u, int f, int s, int dep) {
if(s > k) return;
if(buc[s] > dep) buc[s] = dep, modi.emplace_back(s);
for(auto i : to[u]) {
int v = i.F, w = i.S;
if(!vis[v] && v != f)
dfs2(v, u, s + w, dep + 1);
}
}
void slove(int u, int f, int tot) {
rt = 0;
getrt(u, f, tot);
int r = rt;
vis[r] = 1;
for(auto i : to[r])
if(!vis[i.F]) slove(i.F, r, sz[i.F]);
buc[0] = 0;
for(auto i : to[r]) {
int v = i.F, w = i.S;
if(!vis[v]) {
dfs1(v, u, w, 1);
dfs2(v, u, w, 1);
}
}
buc[0] = inf;
while(!modi.empty()) {
buc[modi.back()] = inf;
modi.pop_back();
}
vis[r] = 0;
}
signed main() {
#ifdef ONLINE_JUDGE
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#endif
cin >> n >> k;
rep(i, 1, n - 1) {
int u, v, w;
cin >> u >> v >> w;
++u, ++v;
to[u].emplace_back(v, w);
to[v].emplace_back(u, w);
}
memset(mx, 0x3f, sizeof mx);
memset(buc, 0x3f, sizeof buc);
slove(1, 0, n);
cout << (ans == inf ? -1 : ans) << endl;
return 0;
}
这份代码在洛谷会 WA 85,当我将第 62 行(slove 函数内)改成这样之后:
if(!vis[i.F]) slove(i.F, r, sz[i.F] + 1);
就 AC 了,我不理解,各位大佬能解答一下吗/kk