This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// In the name of the God
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;
const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 2e5+5;
int n, k, sz[maxn], fen[maxn];
bool mark[maxn];
vector <pii> adj[maxn], vec1, vec2;
void dfs1(int v, int p) {
sz[v] = 1;
for (pii e : adj[v]) {
int u = e.F;
if (!mark[u] and u != p) {
dfs1(u, v); sz[v] += sz[u];
}
}
}
int fcen(int v, int p, int s) {
for (pii e : adj[v]) {
int u = e.F;
if (!mark[u] and u != p and sz[u]*2 > s) return fcen(u, v, s);
}
return v;
}
void dfs2(int v, int p, int mx, int h) {
vec1.pb(mp(mx, h)), vec2.pb(mp(mx, h));
for (pii e : adj[v]) {
int u = e.F;
if (!mark[u] and u != p) dfs2(u, v, max(mx, e.S), h+1);
}
}
void upd(int i, int x) {
for (i += 1; i <= n; i += i&(-i)) fen[i] += x;
}
int get(int i) {
int ans = 0;
for (i += 1; i; i -= i&(-i)) ans += fen[i] ;
return ans;
}
int relax(vector <pii> &vec) {
int res = 0;
sort(all(vec));
for (pii p : vec) {
int j = p.F-k-p.S;
if (j >= 0) res += get(j);
upd(p.S, 1);
}
for (pii p : vec) upd(p.S, -1);
vec.clear();
return res;
}
int cen(int v) {
dfs1(v, v);
v = fcen(v, v, sz[v]);
int ans = 0;
vec2.pb(mp(0, 0));
for (pii e : adj[v]) {
int u = e.F;
if (!mark[u]) {
dfs2(u, v, e.S, 1);
ans -= relax(vec1);
}
}
ans += relax(vec2);
mark[v] = 1;
for (pii e : adj[v]) {
int u = e.F;
if (!mark[u]) ans += cen(u);
}
return ans;
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> k;
for (int i = 1; i < n; i++) {
int v, u, w; cin >> v >> u >> w;
adj[--v].pb(mp(--u, w));
adj[u].pb(mp(v, w));
}
cout << cen(0)*2 << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |