Awesome Shawarma 【Gym - 101991A】【点分治】

题目链接

---

  题意：求给一棵N个点的树，加一条边，使得桥的数量在之间。

  思路：原来有N-1条边，同时也代表N-1个桥，那么，我们需要删除长度的桥，才能使得答案在之间，所以，我们找出长度在的链，统计这样的链的数量，所以，可以用点分治来完成这个任务。

  一开始的时候，我边界条件选择不严谨，导致出现如下错误。

1
6 4 4
1 2
2 3
3 4
4 5
5 6
ans:5

#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
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, ql, qr;
struct Eddge
{
    int nex, to;
    Eddge(int a=-1, int b=0):nex(a), to(b) {}
} edge[maxN << 1];
inline 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); }
int root, maxx, all, siz[maxN], son[maxN];
bool vis[maxN];
void findroot(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;
        findroot(v, u);
        siz[u] += siz[v];
        son[u] = max(son[u], siz[v]);
    }
    son[u] = max(son[u], all - siz[u]);
    if(maxx > son[u]) { maxx = son[u]; root = u; }
}
int deep[maxN], Stap[maxN], Stop, numsiz[maxN];
ll sum[maxN], dpsum[maxN], ans;
void dfs(int u, int fa)
{
    Stap[++Stop] = u;
    deep[u] = deep[fa] + 1; numsiz[u] = 1;
    for(int i=head[u], v; ~i; i=edge[i].nex)
    {
        v = edge[i].to;
        if(vis[v] || v == fa) continue;
        dfs(v, u);
        numsiz[u] += numsiz[v];
    }
}
void Divide(int u)
{
    vis[u] = true;
    int totsiz = all;
    for(int i=0; i<=all + 1; i++) sum[i] = 0;
    sum[0] = 1;
    for(int i=head[u], v; ~i; i=edge[i].nex)
    {
        v = edge[i].to;
        if(vis[v]) continue;
        Stop = 0;
        deep[u] = 0;
        dfs(v, u);
        for(int j=1; j<=Stop; j++) dpsum[deep[Stap[j]]]++;
        for(int j=1; j<=numsiz[v]; j++)
        {
            if(ql - j <= totsiz && qr - j >= -1) ans += (sum[max(0, ql - j)] - sum[min(totsiz, qr - j) + 1]) * dpsum[j];
        }
        for(int j=numsiz[v] - 1; j>=0; j--) dpsum[j] += dpsum[j + 1];
        for(int j=numsiz[v]; j>=0; j--) sum[j] += dpsum[j];
        for(int j=0; j<=numsiz[v] + 1; j++) dpsum[j] = 0;
    }
    for(int i=head[u], v; ~i; i=edge[i].nex)
    {
        v = edge[i].to;
        if(vis[v]) continue;
        all = siz[v] > siz[u] ? totsiz - siz[u] : siz[v];
        maxx = INF;
        findroot(v, 0);
        Divide(root);
    }
}
inline void init()
{
    cnt = 0; ql = N - 1 - R; qr = N - 1 - L; ans = 0;
    for(int i=1; i<=N; i++) { head[i] = -1; vis[i] = false; }
}
int main()
{
    freopen("awesome.in", "r", stdin);
    int T; scanf("%d", &T);
    while(T--)
    {
        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);
        }
        all = N; maxx = INF;
        findroot(1, 0);
        Divide(root);
        printf("%lld\n", ans);
    }
    return 0;
}