2024 Summer_Camp 做题总结 下

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 没修好，气死我也。