# Title:

Give you a tree with an edge weight of 0 at the beginning, then give you n-1 operations, add edge weight to the edge every time, ask you how many pairs of paths between n-1 operations are less than or equal to l, and the edge weight is less than or equal to w

# Explanation:

poj1741 point divide and conquer problem is edge weight sum less than or equal to k, a limit of path number is added here

For the two restrictions of the path number and the edge weight, we can get two inequalities, and we can get an array a satisfying the distance by using the point divide and conquer.

After sorting array a according to the distance from small to large, it can satisfy the condition of cdq. It is also a three-dimensional partial order problem. When counting, we need to pay attention to the weight.

# Code:

```#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 tot;
void add_edge(int u, int v, int w) {
edge[tot].v = v;
edge[tot].w = w;
}

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);
a[++cnt] = node(L - len, W - weight, 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++) {
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;
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);
sort(a + 1, a + cnt + 1);
// for(int i=1;i<=cnt;i++){
//     debug3(a[i].x,a[i].y,a[i].op);
// }
for(int i = 1; i <= cnt; i++) {
if(2 * a[i].x <= L && 2 * a[i].y <= W)
res += a[i].op ^ 1;
}
// debug1(cnt);
return (cdq(1, cnt) - res) / 2;
}
LL solve(int u, int num) {
int root = get_root(u, -1, num);
LL res = Find(root, 0, 0);
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]) {
res -= Find(v, 1, w);
res += solve(v, sz[v] > sz[root] ? num - sz[root] : sz[v]);
}
}
return res;
}
int main() {
#ifndef ONLINE_JUDGE
FIN
#endif
mx[0] = INF;
tot = 0;
scanf("%d%d%d", &n, &L, &W);
for(int i = 2; i <= n; i++) {
int u, w; scanf("%d%d", &u, &w);
}
printf("%lld\n", solve(1, n));
return 0;
}```

Keywords: Python less iOS

Added by Azkoyen on Sat, 26 Oct 2019 21:00:02 +0300