Bình luận

• 
  

  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".