QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#376641#3171. Rooted Subtreesckiseki#WA 107ms32700kbC++201.7kb2024-04-04 14:21:272024-04-04 14:21:27

Judging History

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

  • [2024-04-04 14:21:27]
  • 评测
  • 测评结果:WA
  • 用时:107ms
  • 内存:32700kb
  • [2024-04-04 14:21:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << "\n";
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

constexpr int N = 200000 + 5;
constexpr int K = 20;

vector<int> g[N];

int dep[N];
int tl[N], tr[N], tc;

int pa[N][K];

bool anc(int u, int v) {
  return tl[u] <= tl[v] and tr[v] <= tr[u];
}

int lca(int u, int v) {
  if (anc(u, v))
    return u;
  for (int i = K - 1; i >= 0; --i)
    if (not anc(pa[u][i], v))
      u = pa[u][i];
  return u;
}

void dfs(int u, int f) {
  pa[u][0] = f;
  for (int i = 1; i < K; ++i)
    pa[u][i] = pa[pa[u][i - 1]][i - 1];
  tl[u] = tc++;
  dep[u] = dep[f] + 1;
  for (int v : g[u]) {
    if (v != f)
      dfs(v, u);
  }
  tr[u] = tc;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(0, 0);
  while (q--) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    int64_t d = dep[u] + dep[v] - 2 * dep[lca(u, v)];
    int64_t ans = n;
    ans += d * (d + 1) / 2;
    cout << ans << '\n';
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3624kb

input:

5 2
1 2
2 3
2 4
4 5
1 3
4 5

output:

8
6

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 107ms
memory: 32700kb

input:

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

output:

200120
200210
200136
200406
200190
200351
200190
200276
200276
200378
200210
200105
200378
200105
200078
200253
200210
200231
200231
200300
200190
200078
200210
200276
200378
200300
200078
200276
200300
200253
200091
200276
200091
200496
200435
200325
200300
200171
200325
200153
200300
200091
200325...

result:

wrong answer 1st lines differ - expected: '200153', found: '200120'