CF293E. Close Vertices

发表于 | 阅读数

求树上距离$\leq L$,树上权值距离$\leq W$,点对个数。

求树上距离$\leq L$,即双指针模版题，考虑$(l,r]$区间去合适的，即$query(0,L-dep[l]]$有多少，树状数组维护。

  • 由于边权过大需要离散化，选择维护树上距离
  • 统计时，不能将自己即$dep[l]$，也算入，所以先树状数组移走再查询。
代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
struct BIT
{
    int tr[N];
    int Bmax;
    int lb(int x) { return (-x) & x; }
    int query(int x)
    {
        if (x <= 0)
            return 0;
        int res = 0;
        while (x)
        {
            res += tr[x];
            x -= lb(x);
        }
        return res;
    }
    void update(int x, int w)
    {
        if (x <= 0)
            return;
        while (x <= Bmax)
        {
            tr[x] += w;
            x += lb(x);
        }
    }
} tr;

vector<pii> g[N];

int rt, gcnt;
int vis[N], siz[N];
int f[N];
ll L, W;
void getRoot(int x, int fa)
{
    siz[x] = 1;
    f[x] = 0;
    for (pii now : g[x])
    {
        int to = now.first;
        if (to == fa || vis[to])
            continue;
        getRoot(to, x);
        siz[x] += siz[to];
        f[x] = max(f[x], siz[to]);
    }
    f[x] = max(f[x], gcnt - siz[x]);
    if (f[x] < f[rt])
        rt = x;
}
pii c[N];
int cnt;
void solve(int x, int fa, int deep, int d)
{
    c[++cnt] = mk(deep, d);
    for (pii now : g[x])
    {
        int to = now.first;

        if (to == fa || vis[to])
            continue;
        solve(to, x, deep + now.second, d + 1);
    }
}
ll calc(int x, int deep, int d)
{
    ll res = 0;
    cnt = 0;

    solve(x, 0, deep, d);

    sort(1 + c, 1 + c + cnt);
    for (int i = 1; i <= cnt; i++)
        tr.update(c[i].second + 1, 1);
    int l = 1, r = cnt;
    while (l < r)
    {
        // cout << l << " " << r << endl;
        if (c[l].first + c[r].first <= W)
        {
            tr.update(c[l].second + 1, -1);
            res += tr.query(L - c[l].second + 1);
            l++;
        }
        else
        {
            tr.update(c[r].second + 1, -1);
            r--;
        }
    }
    tr.update(c[l].second + 1, -1);
    return res;
}
ll ans = 0;
void dfs(int x)
{

    ans += calc(x, 0, 0);
    vis[x] = 1;
    for (pii now : g[x])
    {
        int to = now.first;
        if (vis[to])
            continue;
        // cout << to << endl;
        ans -= calc(to, now.second, 1);
        rt = 0;
        gcnt = siz[to];
        getRoot(to, x);
        dfs(rt);
    }
}
int main()
{
    int n = read();
    L = read();
    W = read();

    for (int i = 1; i < n; i++)
    {
        int u = read(), w = read();
        g[i + 1].push_back(mk(u, w));
        g[u].push_back(mk(i + 1, w));
    }
    f[0] = 1e9;
    rt = 0;
    gcnt = n;
    tr.Bmax = 2 * n;
    getRoot(1, 0);
    dfs(rt);
    printf("%lld\n", ans);
}