QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#90592#5020. 举办乘凉州喵,举办乘凉州谢谢喵Rainybunny0 20ms20344kbC++236.1kb2023-03-23 20:36:242023-03-23 20:36:25

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-23 20:36:25]
  • 评测
  • 测评结果:0
  • 用时:20ms
  • 内存:20344kb
  • [2023-03-23 20:36:24]
  • 提交

answer

/*+Rainybunny+*/

#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)
#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)

typedef std::pair<int, int> PII;
#define fi first
#define se second

inline char fgc() {
    static char buf[1 << 17], *p = buf, *q = buf;
    return p == q && (q = buf + fread(p = buf, 1, 1 << 17, stdin), p == q)
    ? EOF : *p++;
}

template <typename Tp = int>
inline Tp rint() {
    Tp x = 0, s = fgc(), f = 1;
    for (; s < '0' || '9' < s; s = fgc()) f = s == '-' ? -f : f;
    for (; '0' <= s && s <= '9'; s = fgc()) x = x * 10 + (s ^ '0');
    return x * f;
}

template <typename Tp>
inline void wint(Tp x) {
    if (x < 0) putchar('-'), x = -x;
    if (9 < x) wint(x / 10);
    putchar(x % 10 ^ '0');
}

const int MAXN = 2e5;
int n, q, fa[MAXN + 5], rad[MAXN + 5], ans[MAXN + 5];
std::vector<int> adj[MAXN + 5];

namespace V {

int dep[MAXN + 5], rt[MAXN + 5], siz[MAXN + 5], son[MAXN + 5], top[MAXN + 5];
struct Query { int r, k, id; };
std::vector<Query> qry[MAXN + 5];

struct SegmentTree {
    static const int MAXND = 4e6; // !
    int node, ch[MAXND][2], siz[MAXND];

    inline void insert(int& u, const int l, const int r, const int x) {
        if (!u) u = ++node;
        ++siz[u];
        if (l == r) return ;
        int mid = l + r >> 1;
        if (x <= mid) insert(ch[u][0], l, mid, x);
        else insert(ch[u][1], mid + 1, r, x);
    }

    inline int merge(const int u, const int v) {
        if (!u || !v) return u | v;
        int w = ++node; siz[w] = siz[u] + siz[v];
        ch[w][0] = merge(ch[u][0], ch[v][0]);
        ch[w][1] = merge(ch[u][1], ch[v][1]);
        return w;
    }

    inline int query(const int u, const int l, const int r,
    const int ql, const int qr) const {
        if (!u) return 0;
        if (ql <= l && r <= qr) return siz[u];
        int mid = l + r >> 1, ret = 0;
        if (ql <= mid) ret += query(ch[u][0], l, mid, ql, qr);
        if (mid < qr) ret += query(ch[u][1], mid + 1, r, ql, qr);
        return ret;
    }
} sgt;

inline void init(const int u) {
    siz[u] = 1, dep[u] = dep[fa[u]] + 1;
    sgt.insert(rt[u], 1, n, dep[u]);
    for (int v: adj[u]) if (v != fa[u]) {
        fa[v] = u, init(v), siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) son[u] = v;
        rt[u] = sgt.merge(rt[u], rt[v]);
    }
}

inline void reorder(const int u, const int tp) {
    top[u] = tp;
    if (son[u]) reorder(son[u], tp);
    for (int v: adj[u]) if (v != fa[u] && v != son[u]) reorder(v, v);
}

inline int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) v = fa[top[v]];
        else u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

inline void hang(int u, const int k, const int id) {
    int las = 0;
    while (u) {
        qry[u].push_back({ rad[id], k, id });
        if (son[u] && rad[id]) {
            ans[id] += k * sgt.query(rt[son[u]], 1, n,
            dep[son[u]], dep[son[u]] + rad[id] - 1);
        }
        if (las && rad[id]) {
            ans[id] -= k * sgt.query(rt[las], 1, n,
            dep[las], dep[las] + rad[id] - 1);
        }
        u = fa[las = top[u]];
    }
}

struct BIT {
    int val[MAXN + 5];
    inline void add(int x, const int k) {
        for (; x <= n; x += x & -x) val[x] += k;
    }
    inline int sum(int x) {
        int ret = 0;
        for (; x; x ^= x & -x) ret += val[x];
        return ret;
    }
} bit;

inline void collect(const int u, const int d, const int k) {
    bit.add(d, k);
    for (int v: adj[u]) if (v != fa[u]) collect(v, d + 1, k);
}

inline void solve(const int u) {
    bit.add(1, 1);
    for (int v: adj[u]) if (v != fa[u] && v != son[u]) collect(v, 2, 1);

    for (auto [r, k, id]: qry[u]) ans[id] += k * bit.sum(r);
    if (son[u]) solve(son[u]);

    bit.add(1, -1);
    for (int v: adj[u]) if (v != fa[u] && v != son[u]) collect(v, 2, -1);
}

} // namespace V

namespace R {

int siz[MAXN + 5], wgt[MAXN + 5], mxh, suh, sum[MAXN + 5], sub[MAXN + 5];
bool vis[MAXN + 5];
std::vector<int> qry[MAXN + 5];

inline void findG(const int u, const int fa, const int all, int& rt) {
    siz[u] = 1, wgt[u] = 0;
    for (int v: adj[u]) if (v != fa && !vis[v]) {
        findG(v, u, all, rt), siz[u] += siz[v];
        wgt[u] = std::max(wgt[u], siz[v]);
    }
    wgt[u] = std::max(wgt[u], all - siz[u]);
    if (!rt || wgt[rt] > wgt[u]) rt = u;
}

inline void collect(const int u, const int fa, int* buc, int& h, const int d) {
    ++buc[d], h = std::max(h, d);
    for (int v: adj[u]) if (v != fa && !vis[v]) collect(v, u, buc, h, d + 1);
}

inline void contri(const int u, const int fa, const int d) {
    for (int id: qry[u]) if (rad[id] >= d) {
        ans[id] += sum[std::min(rad[id] - d, mxh)];
        ans[id] -= sub[std::min(rad[id] - d, suh)];
    }
    for (int v: adj[u]) if (v != fa && !vis[v]) contri(v, u, d + 1);
}

inline void solve(const int u) {
    vis[u] = true;

    collect(u, 0, sum, mxh = 0, 0);
    rep (i, 1, mxh) sum[i] += sum[i - 1];
    for (int id: qry[u]) ans[id] += sum[std::min(rad[id], mxh)];
    for (int v: adj[u]) if (!vis[v]) {
        collect(v, 0, sub, suh = 0, 1);
        rep (i, 1, suh) sub[i] += sub[i - 1];
        contri(v, 0, 1), memset(sub, 0, suh + 1 << 2);
    }
    memset(sum, 0, mxh + 1 << 2);

    for (int v: adj[u]) if (!vis[v]) {
        int rt = 0;
        findG(v, 0, siz[v], rt), solve(rt);
    }
}

} // namespace R

int main() {
    n = rint();
    rep (i, 2, n) {
        int u = rint(), v = rint();
        adj[u].push_back(v), adj[v].push_back(u);
    }

    V::init(1), V::reorder(1, 1);

    q = rint();
    rep (i, 1, q) {
        int u = rint(), v = rint(), w = V::lca(u, v); rad[i] = rint();
        V::hang(u, 1, i), V::hang(v, 1, i), V::hang(w, -2, i);
        R::qry[w].push_back(i);
    }

    int rt = 0; R::findG(1, 0, n, rt), R::solve(rt);
    // rep (i, 1, q) wint(ans[i]), putchar("\n "[i < q]);
    rep (u, 1, n) if (u == V::top[u]) V::solve(u);
    rep (i, 1, q) wint(ans[i]), putchar('\n');
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 20ms
memory: 20344kb

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:

2951
1522
4988
109
133
3728
3656
1579
4974
2039
135
288
4675
135
4954
4988
4974
1511
4981
1
1504
4825
4974
4974
1
27
4960
4669
109
4870
353
3660
693
1554
120
3079
845
201
29
4822
3006
23
29
4325
4960
409
4835
4974
32
308
24
96
115
1650
4981
3879
27
2933
119
24
4864
320
4958
158
4629
2257
1
4958
22
4...

result:

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

Subtask #2:

score: 0
Runtime Error

Test #9:

score: 0
Runtime Error

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:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Runtime Error

Test #25:

score: 0
Runtime Error

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:


result:


Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%