Close Vertices
思路
很明显,这是一道点分治题目,但有两个限制条件,考虑将两个条件排序起来,双指针找第一个条件,树状数组维护第二个条件,但是同一个子树内不能重复统计,所以将答案减去每个子树内的答案。
代码
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
inline int read(){register int x = 0, f = 1;register 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 ^ 48);c = getchar();}return x * f;}
inline void write(int x){if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}
const int N = 4e5 + 10;
int n, k, d, maxn, rt, ans;
int t[N];
int lowbit(int x){return x & (-x);}
void modify(int x, int y){
for (int i = max(x, 1ll); i <= 1e5 + 1; i += lowbit(i)) t[i] += y;
}
int query(int x){
int res = 0;
for (int i = max(x, 1ll); i; i -= lowbit(i)) res += t[i];
return res;
}
struct edge{
int v, w, nxt;
}e[N << 1];
int head[N], cnt;
void add(int u, int v, int w){
e[++cnt] = (edge){v, w, head[u]};
head[u] = cnt;
}
struct node{
int dis, l;
bool operator < (const node &b) const{
if (dis != b.dis) return dis < b.dis;
return l < b.l;
}
}stk1[N], stk2[N];
int mx[N], sz[N], top1, top2, dis[N], l[N];
bool vis[N];
void find(int u, int fa){
sz[u] = 1, mx[u] = 0;
for (int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if (v == fa || vis[v]) continue;
find(v, u);
sz[u] += sz[v];
mx[u] = max(mx[u], sz[v]);
}
mx[u] = max(mx[u], maxn - sz[u]);
if (mx[u] < mx[rt]) rt = u;
}
void dfs(int u, int fa){
stk2[++top2] = (node){dis[u], l[u]};
for (int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if (v == fa || vis[v]) continue;
dis[v] = dis[u] + e[i].w;
l[v] = l[u] + 1;
dfs(v, u);
}
}
void calc(int u){
top1 = 0;
for (int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if (vis[v]) continue;
top2 = 0, dis[v] = e[i].w, l[v] = 1;
dfs(v, u);
sort(stk2 + 1, stk2 + top2 + 1);
for (int j = 1; j <= top2; j++) stk1[++top1] = stk2[j], modify(stk2[j].l + 1, 1);
int l = 1, r = top2;
while (l <= top2){
modify(stk2[l].l + 1, -1);
while (l < r && stk2[l].dis + stk2[r].dis > d) modify(stk2[r--].l + 1, -1);
if (l >= r) break;
ans -= query(k - stk2[l].l + 1);
l++;
}
}
stk1[++top1] = (node){0, 0};
sort(stk1 + 1, stk1 + top1 + 1);
for (int i = 1; i <= top1; i++) modify(stk1[i].l + 1, 1);
int l = 1, r = top1;
while (l <= top1){
modify(stk1[l].l + 1, -1);
while (l < r && stk1[l].dis + stk1[r].dis > d) modify(stk1[r--].l + 1, -1);
if (l >= r) break;
ans += query(k - stk1[l].l + 1);
l++;
}
}
void solve(int u){
vis[u] = 1;
calc(u);
for (int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if (vis[v]) continue;
maxn = sz[v];
rt = 0;
find(v, 0);
solve(rt);
}
}
signed main(){
n = read(), k = read(), d = read();
for (int i = 1; i < n; i++){
int v = read(), w = read();
add(i + 1, v, w), add(v, i + 1, w);
}
maxn = mx[rt] = n;
find(1, 0);
solve(rt);
cout << ans;
return 0;
}
Luogu 的 CF Remotejudge 没修好,气死我也。
标签:rt,Summer,stk1,int,Camp,modify,++,2024,read From: https://www.cnblogs.com/bryceyyds/p/18369580