桥【2021牛客寒假算法基础集训营5 J】【点分治】

题目链接
显然，一棵树有条割边（也指桥），于是如果要使最后只有至条桥，那么当时候，实际上我们要将长度为的链给“取消割边”，而取消割边的方法就是通过连边。一条长度为的边，会产生的贡献。
所以，我们假设现在找到的一个点举例目前的根节点距离为，要找一个根节点的另一个方向的距离为，那么此时产生的贡献是。所以，我们维护一个“个数”，一个“”就可以求解了。
然后，点分治的基本操作了。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define pii pair<int, int>
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e5 + 7;
int N, L, R, head[maxN], cnt;
struct Eddge
{
    int nex, to;
    Eddge(int a=-1, int b=0):nex(a), to(b) {}
} edge[maxN << 1];
void addEddge(int u, int v)
{
    edge[cnt] = Eddge(head[u], v);
    head[u] = cnt ++;
}
inline void _add(int u, int v) { addEddge(u, v); addEddge(v, u); }
void init()
{
    cnt = 0;
    for(int i = 1; i <= N; i ++) head[i] = -1;
}
int ql, qr;
int root, siz[maxN], all, son[maxN], maxx;
bool vis[maxN] = {false};
void fid_root(int u, int fa)
{
    siz[u] = 1; son[u] = 0;
    for(int i = head[u], v; ~i; i = edge[i].nex)
    {
        v = edge[i].to;
        if(vis[v] || v == fa) continue;
        fid_root(v, u);
        siz[u] += siz[v];
        son[u] = max(son[u], siz[v]);
    }
    son[u] = max(son[u], all - siz[u]);
    if(son[u] < maxx)
    {
        maxx = son[u];
        root = u;
    }
}
struct Bit_Tree
{
    ll t[maxN] = {0};
    void add(int i, ll v) { while(i <= N) { t[i] += v; i += lowbit(i); } }
    ll query(int i) { ll ans = 0; while(i) { ans += t[i]; i -= lowbit(i); } return ans; }
} num, sum;
int dis[maxN];
int que[maxN], top, tail;
void dfs(int u, int fa)
{
    que[tail ++] = u;
    for(int i = head[u], v; ~i; i = edge[i].nex)
    {
        v = edge[i].to;
        if(vis[v] || v == fa) continue;
        dis[v] = dis[u] + 1;
        dfs(v, u);
    }
}
ll ans = 0;
void Divide(int u)
{
    vis[u] = true;
    top = tail = 0;
    ll tmp_num, tmp_sum;
    num.add(1, 1);
//    sum.add(1, 0);
    dis[u] = 0;
    for(int i = head[u], v; ~i; i = edge[i].nex)
    {
        v = edge[i].to;
        if(vis[v]) continue;
        dis[v] = dis[u] + 1;
        dfs(v, u);
        for(int j = top, id, x; j < tail; j ++)
        {
            id = que[j];
            x = dis[id];
            if(qr - x < 0) continue;
            tmp_num = num.query(qr - x + 1) - num.query(max(0, ql - x));
            tmp_sum = sum.query(qr - x + 1) - sum.query(max(0, ql - x));
            ans += 6LL * (tmp_num * x + tmp_sum);
        }
        while(top < tail)
        {
            int id = que[top ++];
            int x = dis[id];
            if(x > qr) continue;
            num.add(x + 1, 1);
            sum.add(x + 1, x);
        }
    }
    if(ql == 0) ans ++; //example:(u, u, u)
    for(int i = 0, id, x; i < tail; i ++)
    {
        id = que[i];
        x = dis[id];
        if(x > qr) continue;
        num.add(x + 1, -1);
        sum.add(x + 1, -x);
    }
    num.add(1, -1);
//    sum.add(1, 0);
    int tot_siz = all;
    for(int i = head[u], v; ~i; i = edge[i].nex)
    {
        v = edge[i].to;
        if(vis[v]) continue;
        all = siz[u] > siz[v] ? siz[v] : tot_siz - siz[u];
        maxx = N;
        fid_root(v, u);
        Divide(root);
    }
}
int main()
{
    scanf("%d%d%d", &N, &L, &R);
    init();
    for(int i = 1, u, v; i < N; i ++)
    {
        scanf("%d%d", &u, &v);
        _add(u, v);
    }
    if(L >= N)
    {
        printf("0\n");
        return 0;
    }
    R = min(R, N - 1);
    ql = N - 1 - R; qr = N - 1 - L;
    all = N; maxx = N;
    fid_root(1, 0);
    Divide(root);
    printf("%lld\n", ans);
    return 0;
}
/*
4 1 1
1 2
2 3
3 4
ans:24
4 1 2
1 2
2 3
3 4
ans:42
*/