QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#468336#1163. Another Tree Queries ProblemwcyQwQWA 82ms39880kbC++174.8kb2024-07-08 20:17:072024-07-08 20:17:07

Judging History

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

  • [2024-07-08 20:17:07]
  • 评测
  • 测评结果:WA
  • 用时:82ms
  • 内存:39880kb
  • [2024-07-08 20:17:07]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int N = 2e5 + 10;
vector<int> g[N];
int son[N], top[N], sz[N], dep[N], fa[N], dfn[N], rk[N], tim, n;
LL sdp[N], ssz[N];

void dfs1(int u, int p) {
  fa[u] = p, dep[u] = dep[p] + 1, sz[u] = 1;
  for (int v : g[u]) if (v != p) {
    dfs1(v, u);
    sz[u] += sz[v];
    if (sz[v] > sz[son[u]]) son[u] = v;
  }
}

void dfs2(int u, int t) {
  dfn[u] = ++tim, rk[tim] = u, top[u] = t;
  if (son[u]) dfs2(son[u], t);
  for (int v : g[u]) if (v != son[u] && v != fa[u]) dfs2(v, v);
}

int find(int u, int v) { // the son of u -> v
  while (top[u] != top[v]) {
    if (fa[top[u]] == v) return top[u];
    u = fa[top[u]];
  }
  return son[v];
}

int lca(int u, int v) {
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) swap(u, v);
    u = fa[top[u]];
  }
  if (dep[u] > dep[v]) swap(u, v);
  return u;
}

struct Tag {
  LL x, y, z;
  Tag(LL x = 0, LL y = 0, LL z = 0) : x(x), y(y), z(z) {}
};

struct Node {
  LL sum;
  Tag tg;
  Node(LL sum = 0, Tag tg = Tag()) : sum(sum), tg(tg) {}
};

inline Tag operator+(Tag a, Tag b) { return Tag(a.x + b.x, a.y + b.y, a.z + b.z); }

inline Node operator+(Node a, Node b) { return Node(a.sum + b.sum); }

inline void tag(Node &u, Tag tg, int l, int r) {
  u.sum += (ssz[r] - ssz[l - 1]) * tg.x;
  u.sum += (sdp[r] - sdp[l - 1]) * tg.y;
  u.sum += tg.z * (r - l + 1);
  u.tg = u.tg + tg;
}

struct SGT {
  Node t[N * 4];

  void pushup(int p) { t[p] = t[p * 2] + t[p * 2 + 1]; }

  void pushdown(int p, int l, int r) {
    int m = (l + r) / 2;
    tag(t[p * 2], t[p].tg, l, m);
    tag(t[p * 2 + 1], t[p].tg, m + 1, r);
    t[p].tg = Tag();
  }

  void modify(int p, int l, int r, int ql, int qr, Tag tg) {
    if (ql <= l && r <= qr) return tag(t[p], tg, l, r);
    pushdown(p, l, r);
    int m = (l + r) / 2;
    if (ql <= m) modify(p * 2, l, m, ql, qr, tg);
    if (qr > m) modify(p * 2 + 1, m + 1, r, ql, qr, tg);
    pushup(p);
  }

  void modify(int l, int r, Tag tg) { modify(1, 1, n, l, r, tg); }

  LL query(int p, int l, int r, int ql, int qr) {
    if (ql > qr) return 0;
    if (ql <= l && r <= qr) return t[p].sum;
    pushdown(p, l, r);
    int m = (l + r) / 2;
    if (qr <= m) return query(p * 2, l, m, ql, qr);
    if (ql > m) return query(p * 2 + 1, m + 1, r, ql, qr);
    return query(p * 2, l, m, ql, qr) + query(p * 2 + 1, m + 1, r, ql, qr);
  }

  LL query(int l, int r) { return query(1, 1, n, l, r); }
} sgt;

void mPath(int u, int v, Tag tg) {
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) swap(u, v);
    sgt.modify(dfn[top[u]], dfn[u], tg);
    u = fa[top[u]];
  }
  if (dfn[u] > dfn[v]) swap(u, v);
  sgt.modify(dfn[u], dfn[v], tg); 
}

LL qPath(int u) {
  LL ans = 0;
  while (u) {
    ans += sgt.query(dfn[top[u]], dfn[u]);
    u = fa[top[u]];
  }
  return ans;
}

int main() {
  // freopen("A.in", "r", stdin);
  // freopen("A.out", "w", stdout);
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n - 1; i++) {
    int u, v;
    cin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  dfs1(1, 0), dfs2(1, 1);
  for (int i = 1; i <= n; i++) {
    sdp[i] = sdp[i - 1] + dep[rk[i]];
    ssz[i] = ssz[i - 1] + sz[rk[i]];
  }
  LL s1 = 0, s2 = 0;
  auto calc = [&] (int l, int r) {
    return 1ll * (l + r) * (r - l + 1) / 2;
  };
  int m;
  cin >> m;
  int cnt = 0;
  while (m--) {
    cnt++;
    int op;
    cin >> op;
    if (op == 1) {
      int u, v;
      cin >> u >> v;
      if (dfn[v] >= dfn[u] && dfn[v] <= dfn[u] + sz[u] - 1) {
        s1 += sz[v];
        s2 += sdp[dfn[v] + sz[v] - 1] - sdp[dfn[v] - 1];
        sgt.modify(dfn[v], dfn[v] + sz[v] - 1, Tag(1, 0, 0));
      } else if (dfn[u] >= dfn[v] && dfn[u] <= dfn[v] + sz[v] - 1) {
        int w = find(u, v);
        s1 += n - sz[w];
        s2 += sdp[n] - sdp[dfn[w] + sz[w] - 1] + sdp[dfn[w] - 1];
        sgt.modify(1, n, Tag(1, 0, 0));
        sgt.modify(dfn[w], dfn[w] + sz[w] - 1, Tag(-1, 0, 0));
        mPath(1, v, Tag(0, 0, -sz[w]));
      } else {
        s1 += sz[v];
        s2 += sdp[dfn[v] + sz[v] - 1] - sdp[dfn[v] - 1];
        sgt.modify(dfn[v], dfn[v] + sz[v] - 1, Tag(1, 0, 0));
      }
    } else if (op == 2) {
      int u, v;
      cin >> u >> v;
      int p = lca(u, v);
      s1 += dep[u] + dep[v] - 2 * dep[p] + 1;
      s2 += calc(dep[p], dep[u]) + calc(dep[p], dep[v]) - dep[p];
      mPath(u, p, Tag(0, -1, dep[u] + 1));
      mPath(v, p, Tag(0, -1, dep[v] + 1));
      mPath(p, p, Tag(0, 0, -1));
      if (p != 1) mPath(1, fa[p], Tag(0, 0, dep[u] + dep[v] - 2 * dep[p] + 1));
    } else {
      int u;
      cin >> u;
      cout << s1 * dep[u] + s2 - 2 * qPath(u) << '\n';
    }
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 37820kb

input:

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

output:

1
5

result:

ok 2 number(s): "1 5"

Test #2:

score: -100
Wrong Answer
time: 82ms
memory: 39880kb

input:

200
171 114
50 183
28 68
67 152
139 125
67 55
50 98
106 71
46 42
157 165
42 49
113 12
81 145
105 13
38 96
34 156
24 17
21 191
135 54
174 116
177 157
123 71
95 130
135 193
150 129
25 190
96 93
188 173
90 160
86 187
20 132
199 75
59 195
189 24
40 68
163 83
25 13
73 33
59 50
154 19
146 21
151 67
89 69
...

output:

888
1060
857
1885
2402
1434
3152
2493
5111
4257
4865
4303
6631
5609
8038
8003
5024
10067
7827
10311
9185
6416
13348
8960
13915
15773
10755
9819
9335
13519
19030
25686
17257
20116
14163
16681
12619
21088
12962
20909
27312
23188
26558
20851
16866
25900
16023
22896
16727
29074
20920
32392
21428
34998
2...

result:

wrong answer 1st numbers differ - expected: '826', found: '888'