边分治会被卡吗

suomynonA @ 2023-06-28 23:20:18

by suomynonA @ 2023-06-28 23:21:00

二楼代码

#include <bits/stdc++.h>
const int N = 1e4;
int n, k;
std::vector<std::pair<int, int>> v[N + 1];
namespace Edge_decomposition {

const int N = 2e4, A = 1e7;
struct edge { int x, y, z; }ar[N * 2 + 1];
int v[N * 2 + 1], w[N * 2 + 1], head[N + 1], pre[N * 2 + 1], tot = 1, nd, vis[N * 2 + 1];
void lnk(int x, int y, int z) { v[++tot] = y, w[tot] = z, pre[tot] = head[x], head[x] = tot, ar[tot] = {x, y, z}; }
void link(int x, int y, int z) { lnk(x, y, z), lnk(y, x, z); }
void rebuild(int x, int fa) {
    int pre = x;
    for (auto [i, c] : ::v[x]) if (i != fa) rebuild(i, x), ++nd, link(pre, nd, 0), pre = nd, link(nd, i, c);
}
void work() { nd = n, rebuild(1, 0); }
int siz[N + 1], rt, mn;
void getedge(int x, int fa, int tot) {
    siz[x] = 1;
    for (int i = head[x]; i; i = pre[i]) if (!vis[i] and i != fa) getedge(v[i], i ^ 1, tot), siz[x] += siz[v[i]];
    if (std::max(siz[x], tot - siz[x]) < mn) rt = fa, mn = std::max(siz[x], tot - siz[x]);
}
int cnt[A + 1], ans;
void add(int x, int fa, int d) {
    if (d > k) return ;
    cnt[d] = 1;
    for (int i = head[x]; i; i = pre[i]) if (!vis[i] and i != fa) add(v[i], i ^ 1, d + w[i]);
}
void clr(int x, int fa, int d) {
    if (d > k) return ;
    cnt[d] = 0;
    for (int i = head[x]; i; i = pre[i]) if (!vis[i] and i != fa) clr(v[i], i ^ 1, d + w[i]);
}
void qry(int x, int fa, int d) {
    if (d > k) return ;
    if (cnt[k - d]) { ans = 1; return ; }
    for (int i = head[x]; i; i = pre[i]) if (!vis[i] and i != fa) qry(v[i], i ^ 1, d + w[i]);
}
void solve(int x, int k) {
    vis[x] = vis[x ^ 1] = 1;
    add(ar[x].x, 0, 0), qry(ar[x].y, 0, ar[x].z), clr(ar[x].x, 0, 0);
    getedge(ar[x].x, 0, n);
    if (siz[ar[x].x] > 1) mn = n + 1, getedge(ar[x].x, 0, siz[ar[x].x]), solve(rt, k + 1);
    getedge(ar[x].y, 0, n);
    if (siz[ar[x].y] > 1) mn = n + 1, getedge(ar[x].y, 0, siz[ar[x].y]), solve(rt, k + 1);
}
void clear() { for (int i = 2; i <= tot; ++i) vis[i] = 0; }
void query() { ans = 0, mn = n + 1, getedge(1, 0, n), solve(rt, 0), puts(ans ? "AYE" : "NAY"), clear(); }

}
int q;
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1, x, y, z; i < n; ++i)
        scanf("%d%d%d", &x, &y, &z), v[x].push_back({y, z}), v[y].push_back({x, z});
    Edge_decomposition::work();
    while (q--) scanf("%d", &k), Edge_decomposition::query();
    return 0;
}

by suomynonA @ 2023-06-28 23:21:24

经测试三度化跑得飞快

by suomynonA @ 2023-06-28 23:21:45

solve的递归层数也小于20

by lingfunny @ 2023-06-29 17:27:40

尛拜 suomynonA 大神二