Submission #1711902

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

class LowestCommonAncestor {
public:
  ll vmax, lmax, *depth, **parent;
  vector<ll> *edge;

  LowestCommonAncestor(ll vmax): vmax(vmax) {
    ll p = 1;
    for(lmax = 1; p < vmax; lmax++) p *= 2;
    edge = new vector<ll>[vmax];
    depth = new ll[vmax];
    parent = new ll*[lmax];
    REP(i, 0, lmax) parent[i] = new ll[vmax];
  }

  void init(ll root) {
    dfs(root, -1, 0);
    REP(i, 0, lmax - 1) REP(j, 0, vmax) {
      parent[i + 1][j] = parent[i][j] >= 0 ? parent[i][parent[i][j]] : -1;
    }
  }

  ll query(ll u, ll v) {
    if(depth[u] > depth[v]) swap(u, v);
    REP(i, 0, lmax) if(((depth[v] - depth[u]) >> i) & 1) v = parent[i][v];
    if(u == v) return u;
    for(ll i = lmax - 1; i >= 0; i--) if(parent[i][u] != parent[i][v]) {
      u = parent[i][u];
      v = parent[i][v];
    }
    return parent[0][u];
  }

private:
  void dfs(ll v, ll p, ll d) {
    parent[0][v] = p;
    depth[v] = d;
    REP(i, 0, edge[v].size()) if(edge[v][i] != p) dfs(edge[v][i], v, d + 1);
  }
};

template<typename T> class SegmentTree {
  vector<T> vec;
  ll n;
  T e;
  T (*op)(T, T);

public:
  SegmentTree(ll _n, T _e, T (*_op)(T, T)) : n(1), e(_e), op(_op) {
    while(n < _n) n *= 2;
    vec.resize(n * 2 - 1, e);
  }

  T query(ll a, ll b) { return rquery(a, b, 0, 0, n); }

  void update(ll a, T k) {
    a += n - 1;
    vec[a] = k;
    while(a > 0) {
      a = (a - 1) / 2;
      vec[a] = op(vec[a * 2 + 1], vec[a * 2 + 2]);
    }
  }

private:
  T rquery(ll a, ll b, ll k, ll l, ll r) {
    if(r <= a || b <= l) return e;
    if(a <= l && r <= b) return vec[k];
    T vl = rquery(a, b, k * 2 + 1, l, (l + r) / 2);
    T vr = rquery(a, b, k * 2 + 2, (l + r) / 2, r);
    return op(vl, vr);
  }
};

ll N, A, B, Q, M, K, V[100000];
vector<ll> E[100000];
pll euler[100000];

void dfs(ll v, ll p, ll &cnt) {
  euler[v].first = cnt;
  for(ll u : E[v]) if(u != p) dfs(u, v, cnt);
  euler[v].second = cnt++;
}

int main(void) {
  scanf("%lld", &N);
  REP(i, 0, N - 1) {
    scanf("%lld %lld", &A, &B);
    A--;
    B--;
    E[A].push_back(B);
    E[B].push_back(A);
  }

  ll cnt = 0;
  dfs(0, -1, cnt);

  LowestCommonAncestor lca(N);
  REP(v, 0, N) for(ll u : E[v]) lca.edge[v].push_back(u);
  lca.init(0);

  SegmentTree<ll> segtree(N, 0, [](ll a, ll b) { return a + b; });

  return 0;

  scanf("%lld", &Q);
  while(Q--) {
    scanf("%lld %lld", &M, &K);
    REP(i, 0, M) {
      scanf("%lld", &V[i]);
      V[i]--;
    }

    vector<pll> order(M);
    REP(i, 0, M) order[i] = pll(euler[V[i]].second, V[i]);
    sort(order.begin(), order.end());

    vector<ll> vec(M * 2 - 1);
    REP(i, 0, M) vec[i] = V[i];
    REP(i, 0, M - 1) {
      ll p = order[i + 0].second;
      ll q = order[i + 1].second;
      assert(0 <= p && p < N);
      assert(0 <= q && q < N);
      vec[M + i] = lca.query(p, q);
      assert(0 <= M + i && M + i < M * 2 - 1);
    }
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    ll ans = 0;
    REP(i, 0, M) segtree.update(euler[V[i]].second, 1);
    REP(i, 0, vec.size()) {
      assert(0 <= vec[i] && vec[i] < N);
      assert(0 <= euler[vec[i]].first && euler[vec[i]].first < N);
      assert(0 <= euler[vec[i]].second && euler[vec[i]].second < N);
      ll s = segtree.query(euler[vec[i]].first, euler[vec[i]].second + 1);
      if(s >= K) ans = max(ans, lca.depth[vec[i]]);
    }
    printf("%lld\n", ans);

    REP(i, 0, M) segtree.update(euler[V[i]].second, 0);
  }
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:91:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &N);
                    ^
./Main.cpp:93:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", &A, &B);
                               ^
./Main.cpp:111:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &Q);
                    ^
./Main.cpp:113:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", &M, &K);
                               ^
./Main.cpp:115:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lld", &V[i]);
         ...

Judge Result