QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#468284#1163. Another Tree Queries ProblemwcyQwQWA 9ms38196kbC++174.7kb2024-07-08 20:08:112024-07-08 20:08:12

Judging History

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

  • [2024-07-08 20:08:12]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:38196kb
  • [2024-07-08 20:08:11]
  • 提交

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 = 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);
  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;
  while (m--) {
    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;
}

详细

Test #1:

score: 0
Wrong Answer
time: 9ms
memory: 38196kb

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:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

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