学校 OJ AC,但是 luogu RE on test 20

XiangXunYi @ 2024-08-21 20:53:55

#include <stdio.h>
#include <vector>
using namespace std;
int st1[600000], st2[600000];
struct pbi {
    bool opt;
    int y;
};
vector<pbi> vec1[300000], vec2[300000];
vector<int> g[300000];
namespace cuttree {
int siz[300000], hson[300000], deep[300000], father[300000], top[300000], dfn[300000], rdfn[300000], dcnt;
void dfs1(int u, int fa, int dp) {
    siz[u] = 1;
    deep[u] = dp;
    father[u] = fa;
    for (int v : g[u])
        if (v != fa) {
            dfs1(v, u, dp + 1);
            siz[u] += siz[v];
            if (siz[v] > siz[hson[u]])
                hson[u] = v;
        }
}
void dfs2(int u, int tp) {
    dfn[u] = ++dcnt;
    rdfn[dcnt] = u;
    top[u] = tp;
    if (hson[u] != 0)
        dfs2(hson[u], tp);
    for (int v : g[u])
        if (v != father[u] && v != hson[u])
            dfs2(v, v);
}
void update(int u, int v, int x, bool withoutroot, vector<pbi> *vec) {
    if (deep[u] < deep[v])
        u ^= v ^= u ^= v;
    while (deep[top[u]] > deep[v]) {
        vec[dfn[top[u]]].push_back({ false, x });
        vec[dfn[u] + 1].push_back({ true, x });
        u = father[top[u]];
    }
    vec[dfn[v] + withoutroot].push_back({ false, x });
    vec[dfn[u] + 1].push_back({ true, x });
}
int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (deep[top[u]] < deep[top[v]])
            u ^= v ^= u ^= v;
        u = father[top[u]];
    }
    if (deep[u] > deep[v])
        u ^= v ^= u ^= v;
    return u;
}
}  // namespace cuttree
int n, m, w[300000], ans[300000];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cuttree::dfs1(1, -1, 0);
    cuttree::dfs2(1, 1);
    for (int i = 1; i <= n; ++i) scanf("%d", w + i);
    for (int i = 1, s, t; i <= m; ++i) {
        scanf("%d%d", &s, &t);
        int l = cuttree::lca(s, t);
        cuttree::update(s, l, cuttree::deep[s], false, vec1);
        cuttree::update(l, t, cuttree::deep[s] - (cuttree::deep[l] << 1), true, vec2);
    }
    for (int i = 1; i <= n; ++i) {
        for (auto [opt, k] : vec1[i])
            if (opt)
                --st1[k + 300000];
            else
                ++st1[k + 300000];
        for (auto [opt, k] : vec2[i])
            if (opt)
                --st2[k + 300000];
            else
                ++st2[k + 300000];
        ans[cuttree::rdfn[i]] = st1[w[cuttree::rdfn[i]] + cuttree::deep[cuttree::rdfn[i]] + 300000] +
                                st2[w[cuttree::rdfn[i]] - cuttree::deep[cuttree::rdfn[i]] + 300000];
    }
    for (int i = 1; i < n; ++i) printf("%d ", ans[i]);
    printf("%d\n", ans[n]);
    return 0;
}

by kczw @ 2024-08-21 21:02:11

@XiangXunYi 虽然不知道问题在哪儿，但是开大了能过

#include <stdio.h>
#include <vector>
using namespace std;
int st1[800000], st2[800000];
struct pbi {
    bool opt;
    int y;
};
vector<pbi> vec1[400005], vec2[400005];
vector<int> g[400005];
namespace cuttree {
int siz[400005], hson[400005], deep[400005], father[400005], top[400005], dfn[400005], rdfn[400005], dcnt;
void dfs1(int u, int fa, int dp) {
    siz[u] = 1;
    deep[u] = dp;
    father[u] = fa;
    for (int v : g[u])
        if (v != fa) {
            dfs1(v, u, dp + 1);
            siz[u] += siz[v];
            if (siz[v] > siz[hson[u]])
                hson[u] = v;
        }
}
void dfs2(int u, int tp) {
    dfn[u] = ++dcnt;
    rdfn[dcnt] = u;
    top[u] = tp;
    if (hson[u] != 0)
        dfs2(hson[u], tp);
    for (int v : g[u])
        if (v != father[u] && v != hson[u])
            dfs2(v, v);
}
void update(int u, int v, int x, bool withoutroot, vector<pbi> *vec) {
    if (deep[u] < deep[v])
        u ^= v ^= u ^= v;
    while (deep[top[u]] > deep[v]) {
        vec[dfn[top[u]]].push_back({ false, x });
        vec[dfn[u] + 1].push_back({ true, x });
        u = father[top[u]];
    }
    vec[dfn[v] + withoutroot].push_back({ false, x });
    vec[dfn[u] + 1].push_back({ true, x });
}
int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (deep[top[u]] < deep[top[v]])
            u ^= v ^= u ^= v;
        u = father[top[u]];
    }
    if (deep[u] > deep[v])
        u ^= v ^= u ^= v;
    return u;
}
}  // namespace cuttree
int n, m, w[400005], ans[400005];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cuttree::dfs1(1, -1, 0);
    cuttree::dfs2(1, 1);
    for (int i = 1; i <= n; ++i) scanf("%d", w + i);
    for (int i = 1, s, t; i <= m; ++i) {
        scanf("%d%d", &s, &t);
        int l = cuttree::lca(s, t);
        cuttree::update(s, l, cuttree::deep[s], false, vec1);
        cuttree::update(l, t, cuttree::deep[s] - (cuttree::deep[l] << 1), true, vec2);
    }
    for (int i = 1; i <= n; ++i) {
        for (auto [opt, k] : vec1[i])
            if (opt)
                --st1[k + 400000];
            else
                ++st1[k + 400000];
        for (auto [opt, k] : vec2[i])
            if (opt)
                --st2[k + 400000];
            else
                ++st2[k + 400000];
        ans[cuttree::rdfn[i]] = st1[w[cuttree::rdfn[i]] + cuttree::deep[cuttree::rdfn[i]] + 400000] +
                                st2[w[cuttree::rdfn[i]] - cuttree::deep[cuttree::rdfn[i]] + 400000];
    }
    for (int i = 1; i < n; ++i) printf("%d ", ans[i]);
    printf("%d\n", ans[n]);
    return 0;
}

by kczw @ 2024-08-21 21:06:51

@XiangXunYi 刚刚又试了一下，只要 st1,st2 两个数组在 6\times10^5 基础上多开 7\times10^4左右就已经能过了

by XiangXunYi @ 2024-08-21 21:12:40

问题语句

cuttree::update(l, t, cuttree::deep[s] - (cuttree::deep[l] << 1), true, vec2);

最坏情况下cuttree::deep[s] - (cuttree::deep[l] << 1)=-6e5

感谢大佬提醒，orz

by XiangXunYi @ 2024-08-21 21:20:28

还有

ans[cuttree::rdfn[i]] = st1[w[cuttree::rdfn[i]] + cuttree::deep[cuttree::rdfn[i]] + 300000] + st2[w[cuttree::rdfn[i]] - cuttree::deep[cuttree::rdfn[i]] + 300000];

最坏情况下w[cuttree::rdfn[i]] + cuttree::deep[cuttree::rdfn[i]]=6e5

by XiangXunYi @ 2024-08-21 21:29:52

更正：

cuttree::update(l, t, cuttree::deep[s] - (cuttree::deep[l] << 1), true, vec2);

由于 l 是 s 的父亲，所以 \operatorname{cuttree::deep[l]} \le \operatorname{cuttree::deep[s]}

所以最坏 cuttree::deep[s] - (cuttree::deep[l] << 1) =-3e5