Codeforces 293E 点分治+cdq

Codeforces 293E

传送门：https://codeforces.com/contest/293/problem/E

题意：

给你一颗边权一开始为0的树，然后给你n-1次操作，每次给边加上边权，问你n-1次操作后有有多少对点之间的路径长度小于等于l，并且边权和小于等于w

题解：

poj1741 点分治裸题是 边权和小于等于k，这里加了一个路径条数的限制

对于这个路径条数和边权的两个限制，我们可以得到两个不等式，可以用点分治得到满足距离的一个数组a

将数组a按照距离从小到大排序后，就可以满足cdq的条件了，也是一个三维偏序问题，计数的时候需要注意一下去重

具体解释请看代码注释

代码：

#include <set>

#include <map>

#include <cmath>

#include <cstdio>

#include <string>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define ls rt<<1

#define rs rt<<1|1

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define bug printf("*********\n")

#define FIN freopen("input.txt","r",stdin);

#define FON freopen("output.txt","w+",stdout);

#define IO ios::sync_with_stdio(false),cin.tie(0)

#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"

#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"

#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"

const int maxn = 3e5 + 5;

const int INF = 0x3f3f3f3f;

struct node {

    int x, y;

    int op;

    bool operator < (const node &a) const {

        if(x != a.x) return x < a.x;

        if(y != a.y) return y < a.y;

        return op < a.op;

    }

    node() {};

    node(int _x, int _y, int _op) {

        x = _x, y = _y, op = _op;

    }

} a[maxn], tmp[maxn];

int cnt;

int n, L, W;

struct EDGE {

    int v, w, nxt;

} edge[maxn << 1];

int head[maxn];

int tot;

void add_edge(int u, int v, int w) {

    edge[tot].v = v;

    edge[tot].w = w;

    edge[tot].nxt = head[u];

    head[u] = tot++;

}

int sz[maxn], vis[maxn], mx[maxn];

int get_root(int u, int fa, int num) {

    int y = 0;

    mx[u] = 0;

    sz[u] = 1;

    for(int i = head[u]; i != -1; i = edge[i].nxt) {

        int v = edge[i].v;

        if(!vis[v] && v != fa) {

            int z = get_root(v, u, num);

            // debug3(u, v, z);

            sz[u] += sz[v];

            mx[u] = max(mx[u], sz[v]);

            if(mx[y] > mx[z]) y = z;

        }

    }

    mx[u] = max(mx[u], num - sz[u]);

    return mx[u] < mx[y] ? u : y;

}

void dfs(int u, int fa, int len, int weight) {

    a[++cnt] = node(len, weight, 0);//与根节点的距离和权值  当前点 op为0

    a[++cnt] = node(L - len, W - weight, 1);//还剩下可以走的距离与权值限制  限制  op为1

    for(int i = head[u]; i != -1; i = edge[i].nxt) {

        int v = edge[i].v;

        if(!vis[v] && v != fa) {

            dfs(v, u, len + 1, weight + edge[i].w);

        }

    }

}

LL cdq(int l, int r) {

    if(l == r) return 0;

    int mid = (l + r) >> 1;

    LL ans = cdq(l, mid) + cdq(mid + 1, r);

    int p = l, q = mid + 1, res = 0;

    for(int i = l; i <= r; i++) {//因为左边的x已经小于右边的x了，所以只要比较y就行

        if((p <= mid && (a[p].y < a[q].y || (a[p].y == a[q].y && a[p].op <= a[q].op))) || q > r) {

            res += a[p].op ^ 1;//如果这个点是非限制点，res++

            tmp[i] = a[p++];//恢复现场

        } else {

            ans += a[q].op * res;//如果这个点是限制点,答案就可以增加

            tmp[i] = a[q++];

        }

    }

    for(int i = l; i <= r; i++) {

        a[i] = tmp[i];

    }

    // debug3(l, r, ans);

    return ans;

}

LL Find(int u, int len, int weight) {

    LL res = 0; cnt = 0;

    dfs(u, -1, len, weight);//获取a数组，即满足l，w限制的数组

    // debug1(cnt);

    sort(a + 1, a + cnt + 1);//对x排序

    for(int i = 1; i <= cnt; i++) {

        if(2 * a[i].x <= L && 2 * a[i].y <= W)

            res += a[i].op ^ 1;//不满足条件的，op为0就不满足，

    }

    // debug1(cnt);

    debug1(res);

    return (cdq(1, cnt) - res) / 2;//a，b，b，a是一样的，所以除二

}

LL solve(int u, int num) {

    int root = get_root(u, -1, num);//点分治  找重心

    debug1(root);

    cout<<"1"<<endl;

    LL res = Find(root, 0, 0);//以该重心分治的贡献

    cout<<"root"<<root<<"de gong xian is:   ";

    debug1(res);

    vis[root] = 1;

    for(int i = head[root]; i != -1; i = edge[i].nxt) {

        int v = edge[i].v, w = edge[i].w;

        if(!vis[v]) {

            cout<<"2"<<endl;

            res -= Find(v, 1, w);//因为这个点是由父亲节点跑过来的，所以边长为1的点重复算了需要减去

            // debug1(res);//减去重复的

            res += solve(v, sz[v] > sz[root] ? num - sz[root] : sz[v]);//子树大小的判断

        }

    }

    return res;

}

int main() {

#ifndef ONLINE_JUDGE

    FIN

#endif

    mx[0] = INF;

    memset(head, -1, sizeof(head));

    tot = 0;

    scanf("%d%d%d", &n, &L, &W);

    for(int i = 2; i <= n; i++) {

        int u, w; scanf("%d%d", &u, &w);

        add_edge(i, u, w);

        add_edge(u, i, w);

    }

    printf("%lld\n", solve(1, n));

    return 0;

}