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


    • 0
      kingofgame    12:24 a.m. 29 Tháng 5, 2024

      include <bits/stdc++.h>

      using namespace std;
      typedef long long ll;
      typedef unsigned long long ull;

      define D 320

      define MOD 1000000007

      define INF 5000000000000000001

      define NA -1

      define MASK(i) (1LL << (i))

      define FULLMASK(i) (MASK((i) + 1) - 1)

      define GETBIT(mask, i) (((mask) >> (i)) & 1)

      define GETBITRANGE(mask, l, r) (((mask) & FULLMASK(r)) >> (l))

      define LASTBIT(i) ((i) & (-(i)))

      define ALL(v) (v).begin(), (v).end()

      define v1 vector<ll>

      define v2 vector<v1>

      define v3 vector<v2>

      inline ll max(ll a, ll b){return (a > b) ? a : b;}
      inline ll min(ll a, ll b){return (a < b) ? a : b;}
      template<class T1, class T2>
      bool maximize(T1 &a, T2 b){
      if (a < b){a = b; return true;}
      return false;
      }
      template<class T1, class T2>
      bool minimize(T1 &a, T2 b){
      if (a > b){a = b; return true;}
      return false;
      }
      template<class T>
      void printArr(vector<T> &a, char separator = ' '){
      for(long i = 0; i<a.size(); ++i) cout << a[i] << separator;
      cout << "\n";
      }
      struct Node{
      long val;
      long child1, child2;
      Node (long v = 0){val = v; child1 = child2 = -1;}
      };
      struct P{
      long i, j;
      P(){}
      P(long a, long b){i = a, j = b;}
      };
      struct SegmentTree{
      long n;
      vector<Node> a;
      SegmentTree(long _n){
      n = _n;
      a.resize(1, Node());
      }
      long size(){return a.size();}
      void clear() {a.clear(); n = 0;}
      void update(long i, long val){
      long cur = 0;
      long l = 1, r = n;
      while(l < r){
      long mid = (l + r) >> 1;
      a[cur].val += val;
      if (i <= mid){
      if (a[cur].child1 == -1){a[cur].child1 = a.size(); a.push_back(Node());}
      cur = a[cur].child1;
      r = mid;
      }
      else{
      if (a[cur].child2 == -1){a[cur].child2 = a.size(); a.push_back(Node());}
      cur = a[cur].child2;
      l = mid + 1;
      }
      }
      a[cur].val += val;
      }
      long get(long u, long v, long l, long r, long id){
      if (u > r || v < l) return 0;
      if (u <= l && r <= v) return a[id].val;
      long mid = (l + r) >> 1;
      long ans = 0;
      if (a[id].child1 != -1)
      ans += get(u, v, l, mid, a[id].child1);
      if (a[id].child2 != -1)
      ans += get(u, v, mid + 1, r, a[id].child2);
      return ans;
      }
      long get(long l, long r){
      if (l > n || r <= 0) return 0;
      maximize(l, 1);
      minimize(r, n);
      return get(l, r, 1, n, 0);
      }
      void traverse(long l, long r, long cur, vector

      &b){
      if (l == r){
      b.push_back(P(l, a[cur].val));
      return;
      }
      long mid = (l + r) >> 1;
      if (a[cur].child1 != -1)
      traverse(l, mid, a[cur].child1, b);
      if (a[cur].child2 != -1)
      traverse(mid + 1, r, a[cur].child2, b);
      }
      void traverse(vector

      &a){traverse(1, n, 0, a);}
      };
      long n, k1, k2;
      long max_height = 0;
      vector<vector\<long>> graph;
      vector<SegmentTree> depth;
      ll ans = 0;
      void find_height(long u, long p, long h){
      maximize(max_height, h);
      for(long v:graph[u]){
      if (v == p) continue;
      find_height(v, u, h + 1);
      }
      }
      void dfs(long u, long p, long h){
      depth[u].update(h, 1);
      for(long v:graph[u]){
      if (v == p) continue;
      dfs(v, u, h + 1);
      if (depth[u].size() < depth[v].size()) swap(depth[u], depth[v]);
      vector

      groceries_list;
      depth[v].traverse(groceries_list);
      depth[v].clear();
      for(P item: groceries_list){
      long dis1 = item.i - h;
      long dis2 = k1 - dis1, dis3 = k2 - dis1;
      ans += 1LL * item.j * depth[u].get(h + dis2, h + dis3);
      }
      for(P item: groceries_list)
      depth[u].update(item.i, item.j);
      }
      }
      int main(){
      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
      cin >> n >> k1 >> k2;
      graph.resize(n+1);
      for(long i = 1; i<n; ++i){ long a,b; cin >> a >> b;
      graph[a].push_back(b);
      graph[b].push_back(a);
      }
      find_height(1, 1, 1);
      for(long i = 0; i<=n; ++i)
      depth.push_back(SegmentTree(max_height));
      dfs(1, 1, 1);
      cout << ans << "\n";
      return 0;
      }


      • 0
        N7hoatt    5:47 p.m. 29 Tháng 8, 2023

        Cho một cây gồm \(n\) đỉnh. Hãy đếm số lượng đường đi phân biệt có tối thiểu \(k_1\) cạnh và tối đa \(k_2\) cạnh .

        Input

        • Dòng đầu tiên gồm số nguyên \(n\), \(k_1\) và \(k_2\): số lượng đỉnh độ dài đường đi. Các đỉnh được đánh số từ \(1,2,3,\dots,n\).
        • \(n-1\) dòng sau đó biểu diễn các cạnh. Mỗi dòng gồm hai số nguyên \(a\) và \(b\): có cạnh nối giữa \(a\) và \(b\).

        Output

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

        Constraints

        • \(1\leq k_1 \leq k_2 \leq n\leq 2 \times 10^5\).
        • \(1\leq a,b\leq n\).

        Example

        Test

        Input 
        5 2 3
1 2
2 3
3 4
3 5
        Output 
        6
        Note

        • 1
          nullType    8:19 a.m. 20 Tháng 12, 2022

          The English title is missing an 'I', this should be "Fixed Length Paths II".