CSES - Fixed-Length Paths II | Đường đi độ dài cố định II

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Flower_On_Stone
Dạng bài
Điểm: 2100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một cây gồm \(n\) nút, nhiệm vụ của bạn là đếm số đường đi riêng biệt có tối thiểu \(k_1\) và tối đa \(k_2\) cạnh.

Input

  • Dòng đầu tiên chứa hai số nguyên \(n,k_1\) và \(k_2:\) số nút và độ dài đường đi. Các nút được đánh số \(1,2,…, n.\)
  • Sau đó có \(n − 1\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b:\) có một cạnh nối hai nút \(a\) và \(b\).

Output

  • In một số nguyên: số lượng đường đi.

Constraints

  • \(1≤k_1≤k_2\le n≤2 \cdot 10^5\)
  • \(1≤a,b≤n\)

Example

Sample Input

5 2 3
1 2
2 3
3 4
3 5

Sample Output

6

Bình luận


  • 0
    nujomau6    3:08 p.m. 15 Tháng 10, 2024 ← chỉnh sửa 8

    Arda Güler:

    include<bits/stdc++.h>

    using namespace std;

    define int long long

    define endl '\n'

    const int mxN = 2e5+5;
    vector<int> adj[mxN];
    int mark[mxN], dp[mxN], bit[mxN];
    int k1, k2;
    int ans = 0, mxd = 0;

    void update(int k, int x) {
    for (; k < mxN; k += k&-k)
    bit[k] += x;
    }

    int query(int l, int r) {
    int s = 0, k = r;
    for (; k > 0; k -= k&-k)
    s += bit[k];
    k = l-1;
    for (; k > 0; k -= k&-k)
    s -= bit[k];
    return s + (l == 0);
    }

    int dfs(int s, int p) {
    dp[s] = 1;
    for (auto i: adj[s]) {
    if (i != p && !mark[i]) {
    dp[s] += dfs(i, s);
    }
    }
    return dp[s];
    }

    int dfs2(int s, int p, int n) {
    for (auto i: adj[s]) {
    if (i != p && !mark[i] && dp[i] > n/2) {
    return dfs2(i, s, n);
    }
    }
    return s;
    }

    void dfs3(int s, int p, int d, int flag) {
    if (d > k2) return;
    mxd = max(mxd, d);
    if (flag) update(d, 1);
    else ans += query(max(0LL, k1-d), k2-d);
    for (auto i: adj[s]) {
    if (i != p && !mark[i])
    dfs3(i, s, d+1, flag);
    }
    }

    void solve(int s) {
    dfs(s, 0);
    int ct = dfs2(s, 0, dp[s]);
    mark[ct] = 1;
    mxd = 0;
    for (auto i: adj[ct]) {
    if (!mark[i]) {
    dfs3(i, ct, 1, 0);
    dfs3(i, ct, 1, 1);
    }
    }
    for (int i = 1; i <= mxd; i++)
    update(i, -query(i, i));
    for (auto i: adj[ct]) if (!mark[i]) {
    solve(i);
    }
    }

    signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #ifdef LOCAL
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w", stdout);
    #endif

    int n; cin>>n>>k1>>k2;
for (int i = 1; i < n; i++) {
    int x, y; cin>>x>>y;
    adj[x].push_back(y);
    adj[y].push_back(x);
}
solve(1);
cout<<ans;

    }
    Clang++
    có mấy quả cần tab ý nó mới AC cho

      • 3 bình luận nữa