QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201035#5020. 举办乘凉州喵,举办乘凉州谢谢喵hos_lyric#38 1052ms98204kbC++1413.4kb2023-10-05 07:28:132024-07-04 02:49:21

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 02:49:21]
  • 评测
  • 测评结果:38
  • 用时:1052ms
  • 内存:98204kb
  • [2023-10-05 07:28:13]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


struct Hld {
  int n, rt;
  // needs to be tree
  // vertex lists
  // modified in build(rt) (parent removed, heavy child first)
  vector<vector<int>> graph;
  vector<int> sz, par, dep;
  int zeit;
  vector<int> dis, fin, sid;
  // head vertex (minimum depth) in heavy path
  vector<int> head;

  Hld() : n(0), rt(-1), zeit(0) {}
  explicit Hld(int n_) : n(n_), rt(-1), graph(n), zeit(0) {}
  void ae(int u, int v) {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  void dfsSz(int u) {
    sz[u] = 1;
    for (const int v : graph[u]) {
      auto it = std::find(graph[v].begin(), graph[v].end(), u);
      if (it != graph[v].end()) graph[v].erase(it);
      par[v] = u;
      dep[v] = dep[u] + 1;
      dfsSz(v);
      sz[u] += sz[v];
    }
  }
  void dfsHld(int u) {
    dis[u] = zeit++;
    const int deg = graph[u].size();
    if (deg > 0) {
      int vm = graph[u][0];
      int jm = 0;
      for (int j = 1; j < deg; ++j) {
        const int v = graph[u][j];
        if (sz[vm] < sz[v]) {
          vm = v;
          jm = j;
        }
      }
      swap(graph[u][0], graph[u][jm]);
      head[vm] = head[u];
      dfsHld(vm);
      for (int j = 1; j < deg; ++j) {
        const int v = graph[u][j];
        head[v] = v;
        dfsHld(v);
      }
    }
    fin[u] = zeit;
  }
  void build(int rt_) {
    assert(0 <= rt_); assert(rt_ < n);
    rt = rt_;
    sz.assign(n, 0);
    par.assign(n, -1);
    dep.assign(n, -1);
    dep[rt] = 0;
    dfsSz(rt);
    zeit = 0;
    dis.assign(n, -1);
    fin.assign(n, -1);
    head.assign(n, -1);
    head[rt] = rt;
    dfsHld(rt);
    assert(zeit == n);
    sid.assign(n, -1);
    for (int u = 0; u < n; ++u) sid[dis[u]] = u;
  }

  friend ostream &operator<<(ostream &os, const Hld &hld) {
    const int maxDep = *max_element(hld.dep.begin(), hld.dep.end());
    vector<string> ss(2 * maxDep + 1);
    int pos = 0, maxPos = 0;
    for (int j = 0; j < hld.n; ++j) {
      const int u = hld.sid[j];
      const int d = hld.dep[u];
      if (hld.head[u] == u) {
        if (j != 0) {
          pos = maxPos + 1;
          ss[2 * d - 1].resize(pos, '-');
          ss[2 * d - 1] += '+';
        }
      } else {
        ss[2 * d - 1].resize(pos, ' ');
        ss[2 * d - 1] += '|';
      }
      ss[2 * d].resize(pos, ' ');
      ss[2 * d] += std::to_string(u);
      if (maxPos < static_cast<int>(ss[2 * d].size())) {
        maxPos = ss[2 * d].size();
      }
    }
    for (int d = 0; d <= 2 * maxDep; ++d) os << ss[d] << '\n';
    return os;
  }

  bool contains(int u, int v) const {
    return (dis[u] <= dis[v] && dis[v] < fin[u]);
  }
  int lca(int u, int v) const {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    for (; head[u] != head[v]; ) (dis[u] > dis[v]) ? (u = par[head[u]]) : (v = par[head[v]]);
    return (dis[u] > dis[v]) ? v : u;
  }
  int jumpUp(int u, int d) const {
    assert(0 <= u); assert(u < n);
    assert(d >= 0);
    if (dep[u] < d) return -1;
    const int tar = dep[u] - d;
    for (u = head[u]; ; u = head[par[u]]) {
      if (dep[u] <= tar) return sid[dis[u] + (tar - dep[u])];
    }
  }
  int jump(int u, int v, int d) const {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    assert(d >= 0);
    const int l = lca(u, v);
    const int du = dep[u] - dep[l], dv = dep[v] - dep[l];
    if (d <= du) {
      return jumpUp(u, d);
    } else if (d <= du + dv) {
      return jumpUp(v, du + dv - d);
    } else {
      return -1;
    }
  }
  // [u, v) or [u, v]
  template <class F> void doPathUp(int u, int v, bool inclusive, F f) const {
    assert(contains(v, u));
    for (; head[u] != head[v]; u = par[head[u]]) f(dis[head[u]], dis[u] + 1);
    if (inclusive) {
      f(dis[v], dis[u] + 1);
    } else {
      if (v != u) f(dis[v] + 1, dis[u] + 1);
    }
  }
  // not path order, include lca(u, v) or not
  template <class F> void doPath(int u, int v, bool inclusive, F f) const {
    const int l = lca(u, v);
    doPathUp(u, l, false, f);
    doPathUp(v, l, inclusive, f);
  }

  // (vs, ps): compressed tree
  // vs: DFS order (sorted by dis)
  // vs[ps[x]]: the parent of vs[x]
  // ids[vs[x]] = x, not set for non-tree vertex
  vector<int> ids;
  pair<vector<int>, vector<int>> compress(vector<int> us) {
    // O(n) first time
    ids.resize(n, -1);
    std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
      return (dis[u] < dis[v]);
    });
    us.erase(std::unique(us.begin(), us.end()), us.end());
    int usLen = us.size();
    assert(usLen >= 1);
    for (int x = 1; x < usLen; ++x) us.push_back(lca(us[x - 1], us[x]));
    std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
      return (dis[u] < dis[v]);
    });
    us.erase(std::unique(us.begin(), us.end()), us.end());
    usLen = us.size();
    for (int x = 0; x < usLen; ++x) ids[us[x]] = x;
    vector<int> ps(usLen, -1);
    for (int x = 1; x < usLen; ++x) ps[x] = ids[lca(us[x - 1], us[x])];
    return make_pair(us, ps);
  }
};

////////////////////////////////////////////////////////////////////////////////


int N;
vector<int> A, B;
int Q;
vector<int> X, Y, D;

vector<vector<int>> graph;
Hld hld;


namespace brute {
vector<int> run() {
cerr<<"[brute::run]"<<endl;
  vector<int> ans(Q, 0);
  for (int q = 0; q < Q; ++q) {
    const int x = X[q], y = Y[q];
    const int l = hld.lca(x, y);
    queue<int> que;
    vector<int> dist(N, -1);
    auto reach = [&](int v, int c) -> void {
      if (!~dist[v]) {
        dist[v] = c;
        que.push(v);
      }
    };
    for (int u = x; u != l; u = hld.par[u]) reach(u, 0);
    for (int u = y; u != l; u = hld.par[u]) reach(u, 0);
    reach(l, 0);
    for (; !que.empty(); ) {
      const int u = que.front();
      que.pop();
      for (const int v : graph[u]) reach(v, dist[u] + 1);
    }
    for (int u = 0; u < N; ++u) if (dist[u] <= D[q]) {
      ++ans[q];
    }
  }
  return ans;
}
}  // brute


namespace sub3 {
vector<vector<pair<int, pair<int, int>>>> ess;
vector<int> ans;

vector<int> sz, del;
void dfsSz(int u, int p) {
  sz[u] = 1;
  for (const int v : graph[u]) if (p != v) {
    dfsSz(v, u);
    sz[u] += sz[v];
  }
}
string dfsString(int u, int p) {
  ostringstream oss;
  oss << "[" << u;
  for (const int v : graph[u]) if (!del[v] && p != v) {
    oss << " " << dfsString(v, u);
  }
  oss << "]";
  return oss.str();
}
/// vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
vector<int> par, dep;
vector<vector<int>> uss, fss;
void dfs(int j, int u, int p, int d) {
  par[u] = p;
  dep[u] = d;
  uss[j].push_back(u);
  if ((int)fss[j].size() < d + 1) fss[j].resize(d + 1, 0);
  ++fss[j][d];
  for (const int v : graph[u]) if (!del[v] && p != v) {
    dfs(j, v, u, d + 1);
  }
}
/// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
void solveSubtree(int depth, int r) {
#ifdef LOCAL
  cerr << string(2 * depth, ' ') << "solveSubtree " << dfsString(r, -1) << endl;
#endif
  vector<int> vs;
  for (const int v : graph[r]) if (!del[v]) {
    vs.push_back(v);
  }
  const int len = vs.size();
  /// vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
  sort(vs.begin(), vs.end());
  uss.assign(len, {});
  fss.assign(len + 1, vector<int>(2, 0));
  for (int j = 0; j < len; ++j) {
    dfs(j, vs[j], r, 1);
  }
  int mx = 2;
  for (int j = 0; j < len; ++j) {
    chmax(mx, (int)fss[j].size());
  }
  fss[len].assign(mx, 0);
  par[r] = -1;
  dep[r] = 0;
  ++fss[len][0];
  for (int j = 0; j < len; ++j) {
    for (int d = 0; d < (int)fss[j].size(); ++d) {
      fss[len][d] += fss[j][d];
    }
  }
  for (int j = 0; j <= len; ++j) {
    for (int d = 1; d < (int)fss[j].size(); ++d) {
      fss[j][d] += fss[j][d - 1];
    }
  }
// cerr<<string(2*depth,' ')<<"uss = "<<uss<<", fss = "<<fss<<endl;
  auto get = [&](int j, int d) -> int {
    return fss[j][min(d, (int)fss[j].size() - 1)];
  };
  for (const auto &e : ess[r]) {
    const int q = e.first;
    ans[q] += get(len, D[q]);
    for (const int v : {e.second.first, e.second.second}) {
      const int j = lower_bound(vs.begin(), vs.end(), v) - vs.begin();
      if (j < len && vs[j] == v) {
        ans[q] -= get(j, D[q]);
      }
    }
  }
  for (int j = 0; j < len; ++j) {
    for (const int u : uss[j]) {
      for (const auto &e : ess[u]) {
        const int q = e.first;
        if (par[u] != e.second.first && par[u] != e.second.second && dep[u] <= D[q]) {
          ans[q] += get(len, D[q] - dep[u]);
          ans[q] -= get(j, D[q] - dep[u]);
        }
      }
    }
  }
  /// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
}
void solveRec(int depth, int u) {
  for (; ; ) {
    int vm = -1;
    for (const int v : graph[u]) if (!del[v]) {
      if (!~vm || sz[vm] < sz[v]) {
        vm = v;
      }
    }
    if (!~vm || 2 * sz[vm] <= sz[u]) {
      solveSubtree(depth, u);
      del[u] = 1;
      for (const int v : graph[u]) if (!del[v]) {
        solveRec(depth + 1, v);
      }
      break;
    } else {
      sz[u] -= sz[vm];
      sz[vm] += sz[u];
      u = vm;
    }
  }
}
void centroidDecomp() {
  sz.assign(N, 0);
  dfsSz(0, -1);
  del.assign(N, 0);
  par.resize(N);
  dep.resize(N);
  solveRec(0, 0);
}

vector<int> run() {
cerr<<"[sub3::run]"<<endl;
  ess.assign(N, {});
  for (int q = 0; q < Q; ++q) {
    const int x = X[q], y = Y[q];
    const int l = hld.lca(x, y);
    vector<int> us, vs;
    for (int u = x; u != l; u = hld.par[u]) us.push_back(u);
    us.push_back(l);
    for (int u = y; u != l; u = hld.par[u]) vs.push_back(u);
    reverse(vs.begin(), vs.end());
    us.insert(us.end(), vs.begin(), vs.end());
    const int usLen = us.size();
// cerr<<us<<endl;
    for (int j = 0; j < usLen; ++j) {
      const int uL = (j - 1 >= 0) ? us[j - 1] : -1;
      const int u = us[j];
      const int uR = (j + 1 < usLen) ? us[j + 1] : -1;
      ess[u].emplace_back(q, make_pair(uL, uR));
    }
  }
  ans.assign(Q, 0);
  centroidDecomp();
  return ans;
}
}  // sub3


namespace sub4 {
vector<vector<int>> jss;
int calc(int u, int d) {
  if (!(0 <= d && d < N)) return 0;
  const auto &js = jss[d];
  const int posDis = lower_bound(js.begin(), js.end(), hld.dis[u]) - js.begin();
  const int posFin = lower_bound(js.begin(), js.end(), hld.fin[u]) - js.begin();
  return posFin - posDis;
}
vector<int> run() {
cerr<<"[sub4::run]"<<endl;
  jss.assign(N, {});
  for (int j = 0; j < N; ++j) {
    jss[hld.dep[hld.sid[j]]].push_back(j);
  }
  vector<int> ans(Q, 0);
  for (int q = 0; q < Q; ++q) {
    const int x = X[q], y = Y[q];
    const int l = hld.lca(x, y);
    for (int u = x; u != l; u = hld.par[u]) ans[q] += calc(u, hld.dep[u] + D[q]);
    for (int u = y; u != l; u = hld.par[u]) ans[q] += calc(u, hld.dep[u] + D[q]);
    ans[q] += calc(l, hld.dep[l] + D[q]);
    {
      int d = hld.dep[l];
      int u = l;
      for (int k = D[q]; --k >= 0; ) {
        ans[q] += calc(u, d + k);
        --d;
        u = hld.par[u];
        if (!~u) u = 0;
        ans[q] += calc(u, d + k);
      }
    }
  }
  return ans;
}
}  // sub4


int main() {
  for (; ~scanf("%d", &N); ) {
    A.resize(N - 1);
    B.resize(N - 1);
    for (int i = 0; i < N - 1; ++i) {
      scanf("%d%d", &A[i], &B[i]);
      --A[i];
      --B[i];
    }
    scanf("%d", &Q);
    X.resize(Q);
    Y.resize(Q);
    D.resize(Q);
    for (int q = 0; q < Q; ++q) {
      scanf("%d%d%d", &X[q], &Y[q], &D[q]);
      --X[q];
      --Y[q];
    }
    
    graph.assign(N, {});
    hld = Hld(N);
    for (int i = 0; i < N - 1; ++i) {
      graph[A[i]].push_back(B[i]);
      graph[B[i]].push_back(A[i]);
      hld.ae(A[i], B[i]);
    }
    hld.build(0);
    
    const int maxD = *max_element(D.begin(), D.end());
    
    vector<int> ans;
    if (maxD <= 20) {
      ans = sub4::run();
    } else if (N <= 5000 && Q <= 5000) {
      ans = brute::run();
    } else {
      ans = sub3::run();
    }
    for (int q = 0; q < Q; ++q) {
      printf("%d\n", ans[q]);
    }
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 8ms
memory: 4792kb

input:

4988
1 2
1 3
1 4
4 5
1 6
3 7
3 8
5 9
4 10
6 11
3 12
9 13
11 14
8 15
11 16
1 17
7 18
8 19
18 20
7 21
10 22
15 23
18 24
4 25
24 26
9 27
23 28
3 29
3 30
30 31
11 32
18 33
2 34
32 35
29 36
29 37
19 38
9 39
6 40
25 41
16 42
31 43
6 44
42 45
32 46
27 47
32 48
44 49
7 50
10 51
24 52
46 53
30 54
46 55
39 56...

output:

3226
2028
4988
208
252
3970
3886
2013
4974
2118
308
391
4768
312
4954
4988
4974
1551
4981
12
1856
4825
4974
4974
19
82
4960
4680
208
4870
474
3693
808
1880
213
3394
1203
266
84
4822
3334
70
81
4501
4960
668
4866
4974
113
490
75
163
209
2159
4981
4143
100
3168
232
66
4864
525
4958
390
4713
2305
15
49...

result:

ok 4966 numbers

Test #2:

score: 0
Accepted
time: 7ms
memory: 4832kb

input:

4914
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
27 ...

output:

3378
4914
231
4914
4914
3378
22
4914
4914
2559
4914
75
219
1407
1138
863
24
3890
4914
4914
399
399
13
139
77
4914
4095
3071
4914
23
151
110
1407
43
54
4914
4914
1919
2559
77
735
3071
24
133
479
4914
33
831
4
4914
4914
79
4914
199
3890
3071
73
567
15
75
21
126
4914
4914
203
4914
75
127
62
41
4914
409...

result:

ok 4975 numbers

Test #3:

score: 0
Accepted
time: 395ms
memory: 5108kb

input:

4921
1151 2767
2767 322
322 4451
4451 4867
4867 1265
1265 3197
3197 3890
3890 1052
1052 1407
1407 1578
1578 566
566 2965
2965 260
260 4908
4908 308
308 553
553 2845
2845 4249
4249 1284
1284 73
73 1088
1088 277
277 1878
1878 4128
4128 3609
3609 2126
2126 149
149 3467
3467 1653
1653 4913
4913 3604
360...

output:

4921
3192
3260
3983
949
2080
605
3471
4901
2020
2552
1570
3325
3643
458
1296
3072
3423
3045
2569
1720
3195
1908
4397
1536
2799
3072
2443
3176
3311
1403
1119
842
3028
2387
1903
2303
4921
2149
1974
4153
2053
2888
2344
3264
3709
3443
3601
2571
1207
4519
3745
959
1920
1305
1706
1743
522
1266
2153
1812
1...

result:

ok 4930 numbers

Test #4:

score: 0
Accepted
time: 249ms
memory: 5248kb

input:

4942
877 4180
4180 4409
4409 2233
2233 3491
3491 3459
3459 4501
4501 2192
2192 3539
3539 4379
4379 4346
4346 1553
1553 2100
2100 3426
3426 3461
3461 811
811 2981
2981 1493
1493 610
610 599
599 1741
1741 3216
3216 1646
1646 1016
1016 3757
3757 2570
2570 2900
2900 4649
4649 1014
1014 538
538 4288
4288...

output:

4236
3338
4942
4942
4942
4942
1551
1272
3885
4140
4942
3627
3132
3991
3157
4024
4942
4942
3761
3064
238
4942
4942
4942
4942
4942
2256
4942
649
4496
4942
4942
4491
866
4208
4942
4942
4726
4942
4462
4942
4942
4234
2676
2593
4942
4088
4942
2704
3344
3560
4942
4942
4461
4511
4634
3437
2884
3842
4942
494...

result:

ok 4910 numbers

Test #5:

score: 0
Accepted
time: 320ms
memory: 5048kb

input:

4996
1 2
2 3
1 4
4 5
4 6
3 7
4 8
8 9
3 10
9 11
5 12
7 13
12 14
8 15
8 16
14 17
10 18
15 19
17 20
15 21
19 22
21 23
14 24
20 25
25 26
21 27
20 28
19 29
29 30
24 31
31 32
29 33
27 34
34 35
31 36
27 37
30 38
35 39
38 40
37 41
34 42
41 43
43 44
42 45
36 46
37 47
47 48
47 49
41 50
50 51
46 52
50 53
51 54...

output:

4869
3419
3000
4640
4996
4996
3854
4165
4542
4996
1758
3584
3011
4996
4996
4383
2064
4199
2786
2470
4759
4996
4657
4157
2443
2594
1823
3215
1635
3908
1903
3207
2153
4448
4996
4996
3071
2649
3452
4996
1235
1599
2732
2244
2311
4618
1250
4577
3498
4941
1058
3498
3539
3415
907
4170
4996
4144
2235
2664
4...

result:

ok 4952 numbers

Test #6:

score: 0
Accepted
time: 145ms
memory: 5220kb

input:

4935
1 2
1 3
4 2
5 2
6 4
7 4
8 6
9 6
10 8
11 8
12 10
13 10
14 12
15 12
16 14
17 14
18 16
19 16
20 18
21 18
22 20
23 20
24 22
25 22
26 24
27 24
28 26
29 26
30 28
31 28
32 30
33 30
34 32
35 32
36 34
37 34
38 36
39 36
40 38
41 38
42 40
43 40
44 42
45 42
46 44
47 44
48 46
49 46
50 48
51 48
52 50
53 50
5...

output:

4442
4133
346
3268
4850
3512
3312
3581
4092
4655
2256
3950
3157
3480
4935
4188
4935
1593
1135
4935
4935
4875
4108
3771
4158
4935
4935
3156
3148
1814
4935
3368
4303
2861
4917
2370
3992
4764
2772
4935
4935
2640
4935
4691
2291
4268
1798
4530
3058
3219
4935
3141
4935
2699
4547
2164
2495
3049
370
3409
21...

result:

ok 4992 numbers

Test #7:

score: 0
Accepted
time: 126ms
memory: 4652kb

input:

4919
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
...

output:

2653
3219
4302
1418
1713
713
3341
647
487
1508
971
4851
4443
3078
2380
2267
4171
18
2056
1833
3136
817
4375
4103
3423
433
3967
725
282
2358
4171
1680
3350
2403
802
1855
137
2091
3731
1061
581
1273
4783
133
1911
4239
4233
678
3127
3481
284
1896
435
593
4781
103
4647
1615
1231
2689
574
1833
4783
645
4...

result:

ok 4980 numbers

Test #8:

score: 0
Accepted
time: 509ms
memory: 4916kb

input:

4973
1 4517
2 744
3 1115
4 3191
5 4186
6 4608
7 3898
8 3939
9 1998
10 2287
11 2277
12 4200
13 4935
14 3955
15 3683
16 278
17 547
18 3351
19 2642
20 4050
21 3457
22 2337
23 3435
24 1476
25 4853
26 3985
27 736
28 3016
29 4840
30 3866
31 4567
32 4067
33 3724
34 1872
35 1533
36 4787
37 53
38 1632
39 295...

output:

91
2487
2646
1791
2447
3327
532
1801
1079
1526
1236
77
4028
3401
4103
1573
3540
1641
452
52
2497
3128
2593
734
1293
3213
1786
1626
2130
2033
1935
2673
1758
1838
1284
758
2952
301
947
2875
3073
1462
2615
2842
3561
1969
1416
3088
2476
1082
696
3665
2041
3263
3063
2988
1402
1050
2967
3696
2309
3767
281...

result:

ok 4982 numbers

Subtask #2:

score: 8
Accepted

Test #9:

score: 8
Accepted
time: 433ms
memory: 49764kb

input:

199995
1 2
2 3
2 4
1 5
3 6
5 7
6 8
4 9
2 10
5 11
5 12
1 13
1 14
1 15
13 16
1 17
10 18
16 19
11 20
8 21
17 22
4 23
19 24
7 25
22 26
8 27
14 28
1 29
9 30
3 31
3 32
21 33
19 34
26 35
34 36
5 37
29 38
22 39
5 40
13 41
28 42
8 43
35 44
22 45
14 46
12 47
32 48
11 49
8 50
18 51
23 52
18 53
4 54
6 55
10 56
...

output:

757
69428
2793
181264
91707
182
32496
199183
6399
15975
11640
119051
236
689
15
9532
41
36592
178936
56
45424
193403
90248
3417
949
68
34133
60471
199861
188090
75088
127
1
6
4
3
3
11
61157
199860
199153
155706
196287
192862
53742
51862
179199
428
196282
199989
3613
26
99007
134461
198159
20382
7518...

result:

ok 199996 numbers

Test #10:

score: 0
Accepted
time: 232ms
memory: 49536kb

input:

199993
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
2...

output:

22
31743
62
30
510
6079
94
24063
190
4079
382
30
62
12159
1022
2043
8063
62
4
3063
4079
30
254
46
10
22
6111
12159
16127
22
1
12031
1
94
382
766
4063
254
46
766
1022
62
766
1
22
46
30
8063
8063
254
3063
22
62
30
1
62
254
4
10
15871
1022
46
2039
6079
22
254
1022
16127
30
766
8127
14
14
10
46
1
62
406...

result:

ok 199995 numbers

Test #11:

score: 0
Accepted
time: 662ms
memory: 56596kb

input:

199993
25163 125238
125238 19096
19096 88864
88864 113505
113505 12722
12722 56225
56225 8736
8736 74926
74926 38529
38529 80231
80231 19719
19719 198784
198784 75213
75213 190174
190174 163340
163340 62363
62363 144160
144160 130912
130912 3919
3919 21218
21218 85281
85281 187312
187312 79930
79930...

output:

97095
57496
116181
132482
144412
69917
174677
96334
37980
80902
148979
22074
166530
153392
43419
163281
148526
62703
79363
199993
153733
152298
5085
156125
117973
61925
36346
95741
124148
102890
20093
5408
77598
176994
177809
169850
144418
43786
189237
69098
5167
199993
103575
105198
197612
38829
20...

result:

ok 199994 numbers

Test #12:

score: 0
Accepted
time: 683ms
memory: 69052kb

input:

200000
3219 118490
118490 61372
61372 74390
74390 88375
88375 63918
63918 37580
37580 33219
33219 170480
170480 81737
81737 153202
153202 93921
93921 149109
149109 88339
88339 167037
167037 67099
67099 58363
58363 6784
6784 109386
109386 11895
11895 14872
14872 65638
65638 43958
43958 181669
181669 ...

output:

59633
108235
72863
144596
90365
57521
48069
163045
124462
18633
39115
111210
59413
80420
86945
182373
99188
57011
148702
53778
132289
68037
69705
50797
91155
77852
27499
106082
87174
122445
78221
71755
10125
93101
163451
16175
104215
50130
81182
30091
44299
81429
91045
111890
73099
72278
74017
59177...

result:

ok 199992 numbers

Test #13:

score: 0
Accepted
time: 310ms
memory: 53380kb

input:

199992
1 2
1 3
2 4
2 5
4 6
1 7
5 8
5 9
3 10
6 11
4 12
4 13
6 14
5 15
9 16
11 17
17 18
13 19
18 20
14 21
18 22
17 23
21 24
19 25
25 26
25 27
27 28
21 29
20 30
29 31
23 32
31 33
33 34
34 35
28 36
33 37
28 38
38 39
30 40
33 41
33 42
38 43
41 44
44 45
44 46
41 47
45 48
41 49
47 50
49 51
42 52
50 53
44 5...

output:

40732
40074
40815
13444
89657
22422
23494
61358
102922
66209
62228
32272
77095
68562
27799
74336
45129
71632
68525
13022
71347
63735
92178
64200
90446
50728
83632
61441
43695
10496
35481
81587
75266
77943
56182
14188
46302
108160
84166
3192
52959
522
57676
28165
97982
15371
95012
3437
53633
49240
55...

result:

ok 199998 numbers

Test #14:

score: 0
Accepted
time: 270ms
memory: 61272kb

input:

199990
1 2
1 3
4 2
5 2
6 4
7 4
8 6
9 6
10 8
11 8
12 10
13 10
14 12
15 12
16 14
17 14
18 16
19 16
20 18
21 18
22 20
23 20
24 22
25 22
26 24
27 24
28 26
29 26
30 28
31 28
32 30
33 30
34 32
35 32
36 34
37 34
38 36
39 36
40 38
41 38
42 40
43 40
44 42
45 42
46 44
47 44
48 46
49 46
50 48
51 48
52 50
53 50...

output:

59224
71441
128293
104009
42824
136779
12532
93560
81095
108628
176617
63487
103752
175849
36193
178489
73311
34313
46423
75989
76344
145231
20076
127399
81148
17356
39455
99025
44904
3548
78503
135455
28
136931
58140
53161
33288
134084
67877
26048
51868
74301
139992
165315
126781
136117
28112
86333...

result:

ok 199996 numbers

Test #15:

score: 0
Accepted
time: 210ms
memory: 49796kb

input:

199997
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 5...

output:

65710
203
400
304
388
328
441
19
417
49
311
329
193
71968
895
179
152645
282
7600
185
150933
150045
444
3693
56770
34420
8765
335
73751
4665
3
203
380
44479
392
356
113
373
46663
143312
234
265
386
378
339
184360
404
21904
9861
393
445
441
91
299
9
213
24586
65263
22235
121
35761
169
36121
435
40035...

result:

ok 199995 numbers

Test #16:

score: 0
Accepted
time: 575ms
memory: 49052kb

input:

199997
1 64008
2 4187
3 154904
4 191579
5 107782
6 29053
7 123085
8 191601
9 95335
10 164039
11 171804
12 145532
13 104884
14 19820
15 74055
16 14172
17 98802
18 144668
19 188276
20 173096
21 62815
22 133749
23 65035
24 161785
25 191028
26 84730
27 176488
28 173295
29 110316
30 121532
31 81037
32 81...

output:

135622
123942
47301
113894
93180
10469
9237
13166
2896
20323
182669
26483
168662
47202
7900
7785
129591
1577
17943
5638
16670
16980
32760
153668
394
142656
30298
1801
167880
25099
10860
39103
28660
158337
55
126816
57661
17387
11147
95051
3
13130
28040
163801
141
109445
110915
13173
56634
20527
6325...

result:

ok 199993 numbers

Subtask #3:

score: 23
Accepted

Dependency #2:

100%
Accepted

Test #17:

score: 23
Accepted
time: 616ms
memory: 60052kb

input:

199996
1 2
2 3
3 4
1 5
1 6
4 7
1 8
5 9
4 10
4 11
7 12
11 13
7 14
10 15
2 16
1 17
9 18
10 19
9 20
13 21
8 22
14 23
21 24
8 25
20 26
23 27
17 28
6 29
9 30
9 31
14 32
14 33
6 34
7 35
35 36
31 37
37 38
2 39
12 40
16 41
18 42
3 43
27 44
4 45
7 46
24 47
16 48
44 49
10 50
11 51
9 52
16 53
39 54
30 55
4 56
...

output:

190330
676
6
462
40
5
180041
3
9236
4
7780
72
19848
100092
66812
28617
39645
66797
22
12
957
2542
7
68308
382
96
217
50
44
227
12909
1519
54616
1682
27
124101
45
12279
173381
10
33
21516
147537
59
40
5332
183402
67257
4281
7
172420
498
154897
113480
208
174
1
497
172594
1098
788
13628
39540
3716
748...

result:

ok 199999 numbers

Test #18:

score: 0
Accepted
time: 449ms
memory: 60364kb

input:

199996
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
2...

output:

1533
3063
6
30
23551
15871
15871
24063
30
16127
1022
12159
10
1021
254
14
190
12159
510
1533
190
8127
3055
1022
94
24063
766
766
94
254
38
62
8063
10
6
22
1533
24063
1531
1022
30
4079
6079
766
16127
190
2043
8127
510
62
126
8063
126
126
48444
15871
4079
16
6111
22
6
10
78
30
254
94
15871
4
254
1021
...

result:

ok 200000 numbers

Test #19:

score: 0
Accepted
time: 957ms
memory: 74028kb

input:

199995
11041 115179
115179 153668
153668 847
847 108504
108504 29146
29146 69344
69344 97959
97959 9751
9751 161877
161877 181430
181430 34952
34952 189883
189883 115070
115070 183758
183758 82663
82663 166540
166540 32583
32583 98368
98368 134401
134401 177593
177593 20320
20320 84802
84802 71314
7...

output:

130387
9664
11547
91275
69020
68292
133814
4062
77306
61282
135928
73117
110236
103657
45122
57716
71794
147915
130944
51863
118043
70186
3280
145614
126093
73581
69331
53113
47390
148553
125773
9218
4978
58747
152237
79990
104530
37955
88353
26213
133365
186683
125906
71589
170278
141966
124506
906...

result:

ok 199990 numbers

Test #20:

score: 0
Accepted
time: 1052ms
memory: 98204kb

input:

199993
177390 147612
147612 4211
4211 14815
14815 169902
169902 107796
107796 87432
87432 66581
66581 144789
144789 48284
48284 124832
124832 151850
151850 145877
145877 31550
31550 71569
71569 63733
63733 951
951 6788
6788 199487
199487 114893
114893 11399
11399 170687
170687 122411
122411 46734
46...

output:

107762
141285
24282
123780
66318
114627
45030
82414
56308
6384
104567
96050
91967
43940
151582
70456
69859
121641
60747
102655
183088
79543
155264
136617
108988
104594
43276
168667
110178
40707
29012
62994
22555
14804
27491
65920
22536
58571
192497
122141
47921
104042
112261
96620
126104
111319
9733...

result:

ok 199994 numbers

Test #21:

score: 0
Accepted
time: 482ms
memory: 67952kb

input:

199993
1 2
1 3
2 4
1 5
3 6
1 7
5 8
7 9
9 10
7 11
3 12
6 13
4 14
5 15
8 16
14 17
10 18
10 19
15 20
20 21
19 22
13 23
15 24
17 25
22 26
26 27
20 28
28 29
21 30
21 31
25 32
23 33
25 34
31 35
28 36
30 37
34 38
31 39
34 40
36 41
32 42
37 43
42 44
39 45
42 46
41 47
38 48
43 49
40 50
42 51
50 52
49 53
47 5...

output:

51578
38667
1524
13459
21140
3826
59246
2246
47429
55781
53983
77239
20185
106208
53791
70701
8913
35683
57133
100232
55601
50968
69940
56442
18980
6305
94853
29355
52681
96168
83317
11505
21769
51959
100713
61485
514
47185
100363
84120
36280
64865
55201
65700
7318
24265
82609
20438
5870
73828
86460...

result:

ok 199992 numbers

Test #22:

score: 0
Accepted
time: 440ms
memory: 71776kb

input:

199996
1 2
1 3
4 2
5 2
6 4
7 4
8 6
9 6
10 8
11 8
12 10
13 10
14 12
15 12
16 14
17 14
18 16
19 16
20 18
21 18
22 20
23 20
24 22
25 22
26 24
27 24
28 26
29 26
30 28
31 28
32 30
33 30
34 32
35 32
36 34
37 34
38 36
39 36
40 38
41 38
42 40
43 40
44 42
45 42
46 44
47 44
48 46
49 46
50 48
51 48
52 50
53 50...

output:

61674
63693
5444
4412
119192
97999
68341
140082
55497
42858
77523
54267
167822
49345
20816
48970
131851
179687
94880
43274
93973
118005
52804
91728
102191
94963
103067
30400
99910
161391
7340
68917
67420
88327
12228
104409
151035
80497
90523
116958
77993
61410
100229
69813
145161
121525
19553
14452
...

result:

ok 199992 numbers

Test #23:

score: 0
Accepted
time: 500ms
memory: 85364kb

input:

199991
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 5...

output:

59
48
415
291
69
119538
321
272
334
54
214
41286
367
13805
97857
104
241
255
283
91
323
161
357
125045
132
339
151823
80847
65651
115686
29503
218
53641
258
23
77332
288
45
73
66967
152
299
23692
98685
75
131750
139781
98
350
357
26
4232
254
178
57217
77332
239
448
11508
264
16540
398
117035
405
14
...

result:

ok 199993 numbers

Test #24:

score: 0
Accepted
time: 819ms
memory: 63092kb

input:

199995
1 113414
2 2284
3 98845
4 44695
5 160127
6 100466
7 194555
8 16596
9 144228
10 80166
11 163524
12 104617
13 156298
14 190763
15 190200
16 51669
17 159037
18 3883
19 169292
20 129486
21 109285
22 177749
23 42088
24 110131
25 34729
26 20820
27 157541
28 11756
29 138395
30 24135
31 153422
32 191...

output:

109204
39278
62211
134886
9
601
181082
41676
2033
116851
72120
27639
11577
38351
77170
54255
33378
82327
102402
74545
8152
64128
31796
148495
415
54543
1354
47764
41935
52287
142939
122745
32683
1725
170345
41430
20010
48221
24637
34819
153209
10982
113155
18968
34947
162078
2043
106717
190000
1108
...

result:

ok 199999 numbers

Subtask #4:

score: 0
Time Limit Exceeded

Test #25:

score: 22
Accepted
time: 810ms
memory: 41876kb

input:

199991
1 2
2 3
3 4
3 5
5 6
3 7
1 8
8 9
8 10
10 11
1 12
1 13
13 14
4 15
12 16
13 17
17 18
8 19
3 20
9 21
16 22
10 23
1 24
7 25
6 26
12 27
4 28
21 29
27 30
30 31
21 32
19 33
20 34
17 35
7 36
13 37
24 38
37 39
30 40
31 41
15 42
9 43
32 44
41 45
18 46
38 47
8 48
35 49
13 50
35 51
47 52
35 53
48 54
44 55...

output:

78
107329
190250
5672
110415
199160
3826
96672
75
13429
149
58
704
199639
25
190454
489
198350
197627
10273
172193
192719
99
191654
80328
481
195140
170809
120515
290
199616
719
142
195166
2607
20737
135444
199768
2433
164666
180527
198261
14511
53672
69060
185790
110874
639
131
2130
188357
150164
2...

result:

ok 199996 numbers

Test #26:

score: 0
Accepted
time: 507ms
memory: 40932kb

input:

199992
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
2...

output:

1471
48440
199992
231
2687
31
114687
114687
13823
114
106495
163839
783
25599
199992
12799
73727
199992
431
196607
26623
414
27960
22
11135
60728
7551
167224
199992
231
199992
77823
25599
199992
15359
163839
15359
167224
113
4735
1439
45055
163839
391
56632
2159
24063
65
1439
383
62
57
1327
163839
4...

result:

ok 199992 numbers

Test #27:

score: -22
Time Limit Exceeded

input:

199999
3860 158798
158798 118869
118869 87485
87485 146359
146359 191153
191153 55478
55478 180863
180863 50335
50335 96889
96889 48813
48813 98038
98038 187938
187938 87677
87677 134328
134328 38608
38608 80793
80793 70631
70631 193550
193550 97635
97635 158355
158355 67072
67072 186681
186681 1915...

output:


result:


Subtask #5:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Test #33:

score: 20
Accepted
time: 118ms
memory: 13032kb

input:

49994
1 2
1 3
1 4
4 5
4 6
2 7
5 8
2 9
5 10
3 11
11 12
5 13
2 14
5 15
14 16
15 17
15 18
11 19
7 20
2 21
1 22
21 23
15 24
22 25
16 26
22 27
16 28
11 29
17 30
21 31
3 32
22 33
3 34
33 35
34 36
17 37
22 38
21 39
22 40
11 41
14 42
30 43
42 44
27 45
41 46
21 47
5 48
17 49
40 50
31 51
23 52
40 53
17 54
39 ...

output:

49991
27842
12698
41582
41674
49129
139
49931
49986
49966
33701
41907
520
7
49823
37296
45378
43279
22
45415
43709
139
1658
12239
1106
48337
42014
49964
1603
49935
1295
38134
484
49771
13800
36652
12183
1503
49825
148
49211
195
46766
38915
49990
26440
26888
1176
140
37080
8196
5750
49964
49612
49935...

result:

ok 49997 numbers

Test #34:

score: 0
Accepted
time: 81ms
memory: 12808kb

input:

49994
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
27...

output:

13823
49994
49994
24
367
48
19455
367
2175
6655
1215
3839
17407
9727
49994
28671
49994
3039
49994
49151
1071
3839
3839
49994
1215
49994
671
3839
49994
591
3711
49994
15359
49994
28
2175
367
28671
10751
49994
11263
98
107
41802
4543
199
36863
49994
49994
1183
367
49151
40959
1071
2111
6655
11263
1927...

result:

ok 49997 numbers

Test #35:

score: -20
Time Limit Exceeded

input:

49992
18276 49801
49801 29872
29872 18038
18038 5160
5160 47615
47615 9368
9368 48020
48020 18919
18919 22293
22293 28784
28784 26366
26366 16335
16335 996
996 28965
28965 7132
7132 9570
9570 22976
22976 16634
16634 22619
22619 28051
28051 11004
11004 1360
1360 41340
41340 43214
43214 24436
24436 46...

output:


result:


Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

0%