CSES Fixed Length Paths II
// compile: make data
// run: time ./data < mid.in
#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) _debug_print(#x, x);
#define Debug(x...) _debug_print_format(#x, x);
std::ifstream terminal("/dev/tty");
#define PP cerr<<"\033[1;30mpause...\e[0m",terminal.ignore();
#else
#define debug(x...)
#define Debug(x...)
#define PP
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define VI vector<int>
#define VII vector<vector<int>>
#define VIII vector<vector<vector<int>>>
#define rep(i,a,b) for(int i=(a);i<(int)(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define FIND(a, x) ((find(a.begin(),a.end(),(x))!=a.end())?1:0)
#define cmin(x,...) x=min({(x), __VA_ARGS__})
#define cmax(x,...) x=max({(x), __VA_ARGS__})
#define INTMAX (int)(9223372036854775807)
#define INF (int)(1152921504606846976)
#define NaN (int)(0x8b88e1d0595d51d1)
#define double long double
#define MAXN 200010
 
int n, A, B;
vector<int> e[MAXN];
int tsize[MAXN], depth[MAXN], height[MAXN];
bool removed[MAXN];
void builddfs(int u, int pre) {
    tsize[u] = 1;
    depth[u] = !~pre ? 0 : depth[pre] + 1;
    height[u] = 1;
    for (int v: e[u]) {
        if (v == pre || removed[v]) continue;
        builddfs(v, u);
        tsize[u] += tsize[v];
        cmax(height[u], height[v] + 1);
    }
}
 
int centroid(int r) {
    // builddfs(r, -1);
    int N = tsize[r];
    if (N <= 2) return r;
    int p = -1;
    for (int x = r; ; ) {
        int maxsz = -INF, maxnode = -1;
        for (auto y: e[x]) if (y != p && !removed[y] && tsize[y] > maxsz) maxsz = tsize[y], maxnode = y;
        if (maxsz <= N / 2) return x;
        p = x;
        x = maxnode;
    }
    return r;
}
 
int cur[MAXN], cnt[MAXN];
long long sum[MAXN];
 
long long getsum(int i, int l, int r, int m) {
    if (r >= m) r = m-1;
    if (l < 0) l = 0;
    if (l > r) return 0;
    return sum[r] - (l ? sum[l-1] : 0) - (i<=r && i>=l);
}
 
long long calc(int *a, int m) {
    memset(sum, 0, sizeof(long long)*m);
    sum[0] = a[0]; rep(i, 1, m) sum[i] = sum[i-1] + a[i];
    long long res = 0;
    rep(i, 0, m) res += a[i] * getsum(i, A-i, B-i, m);
    return res / 2;
};
 
long long answer = 0;
 
int qx[MAXN], qy[MAXN];
void getvs(int *a, int u, int r, int base) {
    int head = 0, tail = 0;
    qx[0] = u, qy[0] = r;
    while (head <= tail) {
        int x = qx[head], p = qy[head++];
        if (depth[x]-base > B) continue;
        ++a[depth[x]-base];
        for (auto y: e[x]) if (!removed[y] && y != p) qx[++tail] = y, qy[tail] = x;
    }
};
 
void cddfs(int x) {
    int c = centroid(x);
    if (c != x) builddfs(c, -1);
    int base = depth[c];
    if (tsize[c] < A/2) return;
    memset(cnt, 0, sizeof(int)*height[c]);
    cnt[0] = 1;
    for (auto y: e[c]) if(!removed[y]) {
        memset(cur, 0, sizeof(int)*height[c]);
        getvs(cur, y, c, base);
        answer -= calc(cur, height[c]);
        rep(i, 0, height[c]) cnt[i] += cur[i];
    }
    answer += calc(cnt, height[c]);
    removed[c] = 1;
    for (auto v: e[c]) if (!removed[v]) cddfs(v);
}
 
int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
 
    scanf("%d%d%d", &n, &A, &B);
    rep(i, 0, n-1) {
        int u, v; scanf("%d%d", &u, &v);
        e[u-1].push_back(v-1);
        e[v-1].push_back(u-1);
    }
    builddfs(0, -1);
    cddfs(0);
    printf("%lld\n", answer);
 
    return 0;
}
No Comments

Send Comment Edit Comment


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
Previous
Next