Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- using ll = long long;
- const int N = 4e4 + 10;
- const int M = 1e9;
- class Segment {
- private:
- struct Node {
- int lson, rson;
- int sum;
- } node[N << 5];
- int idx;
- public:
- #define ls(x) node[x].lson
- #define rs(x) node[x].rson
- void init () {
- idx = 0;
- node[idx] = {0, 0, 0};
- }
- void push_up (int p) {
- node[p].sum = node[ls(p)].sum + node[rs(p)].sum;
- }
- int update (int p, int x, int v, int s, int t) {
- if (!p) {
- p = ++ idx;
- node[p] = {0, 0, 0};
- }
- if (s == t) {
- node[p].sum += v;
- return p;
- }
- int mid = (s + t) >> 1;
- if (x <= mid) ls(p) = update(ls(p), x, v, s, mid);
- else rs(p) = update(rs(p), x, v, mid + 1, t);
- push_up(p);
- return p;
- }
- int query (int p, int l, int r, int s, int t) {
- if (!p) return 0;
- if (l <= s && t <= r) {
- return node[p].sum;
- }
- int mid = (s + t) >> 1;
- int res = 0;
- if (l <= mid) res = query(ls(p), l, r, s, mid);
- if (mid < r) res += query(rs(p), l, r, mid + 1, t);
- return res;
- }
- };
- Segment seg;
- int n;
- int lim_l, lim_w;
- vector<pair<int, int>> t[N];
- bool vis[N];
- void init () {
- cin >> n >> lim_l >> lim_w;
- for (int i = 1; i <= n; i ++) {
- t[i].clear();
- vis[i] = 0;
- }
- for (int i = 2; i <= n; i ++) {
- int p, w;
- cin >> p >> w;
- t[p].push_back({i, w});
- t[i].push_back({p, w});
- }
- }
- int sz[N], mx[N], rt, tot;
- void findroot (int x, int fa) {
- sz[x] = 1;
- mx[x] = 0;
- for (auto [y, w]: t[x]) {
- if (y == fa || vis[y]) continue;
- findroot(y, x);
- sz[x] += sz[y];
- mx[x] = max(mx[x], sz[y]);
- }
- mx[x] = max(mx[x], tot - mx[x] - 1);
- if (mx[x] < mx[rt]) rt = x;
- }
- ll ans = 0, ans2 = 0;
- vector<pair<int, int>> vec;
- void add (int x, int fa, int len, int weight) {
- vec.push_back({len, weight});
- for (auto [y, w]: t[x]) {
- if (y == fa || vis[y]) continue;
- add(y, x, len + 1, weight + w);
- }
- }
- void cal (int x, int fa, int opt) {
- seg.init();
- int seg_rt = 0;
- vec.clear();
- if (opt < 0) vec.push_back({1, -opt});
- for (auto [y, w]: t[x]) {
- if (y == fa || vis[y]) continue;
- if (opt > 0) add(y, x, 1, w);
- else add(y, x, 2, w - opt);
- }
- sort(vec.begin(), vec.end());
- int p = vec.size() - 1;
- for (auto [len, w]: vec) {
- if (p < 0 || len > lim_l) break;
- if (len + vec[p].first <= lim_l) {
- seg_rt = seg.update(seg_rt, w, 1, 0, M);
- } else if (p >= 0) {
- if (vec[p].second <= lim_w) {
- int res = seg.query(seg_rt, 0, lim_w - vec[p].second, 0, M);
- // cout << vec[p].first << ' ' << vec[p].second << ' ' << res << endl;
- if (opt > 0) ans += res;
- else ans -= res;
- }
- p --;
- }
- }
- while (p >= 0) {
- if (vec[p].second < lim_w) {
- int res = seg.query(seg_rt, 0, lim_w - vec[p].second, 0, M);
- // cout << vec[p].first << ' ' << vec[p].second << ' ' << res << endl;
- if (opt > 0) ans += res;
- else ans -= res;
- }
- p --;
- }
- if (opt > 0) {
- cout << "add: " << fa << " -> " << x << endl;
- for (auto [len, w]: vec) {
- if (len > lim_l) break;
- if (w <= lim_w) ans2 ++;
- }
- }
- }
- void dfz (int x, int fa) {
- // cout << "dfz: " << fa << " -> " << x << endl;
- vis[x] = 1;
- cal(x, fa, 1);
- // cout << "add: " << ans << endl;
- for (auto [y, w]: t[x]) {
- if (y == fa || vis[y]) continue;
- cal(y, x, -w);
- // cout << "del: " << y << ' ' << ans << endl;
- }
- for (auto [y, w]: t[x]) {
- if (y == fa || vis[y]) continue;
- tot = sz[y];
- rt = 0;
- findroot(y, x);
- findroot(rt, 0);
- dfz(rt, x);
- }
- }
- void solve () {
- init();
- tot = n;
- rt = 0;
- mx[rt] = n;
- findroot(1, 0);
- findroot(rt, 0);
- dfz(rt, 0);
- cout << ans / 2 + ans2 << endl;
- cout << ans << ' ' << ans2 << endl;
- }
- signed main () {
- ios::sync_with_stdio(0);
- cin.tie(0);
- int _ = 1;
- // cin >> _;
- while (_ --) {
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement