样例没过求调

P3806 【模板】点分治 1

Svemit @ 2023-02-03 13:29:37

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long ull;
const int N = 1e5 + 5, M = 1e7 + 5, INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;

int n, m, k;
int q[N], p[N];
int ans[M];
bool st[N];
struct edge
{
    int v, w;
    edge(int v = 0, int w = 0):v(v), w(w){};
};
vector<edge> e[N];

int get_siz(int u, int fa)
{
    if(st[u]) return 0;
    int siz = 1;
    for(auto i:e[u])
    {
        int v = i.v;
        if(v == fa) continue;
        siz += get_siz(v, u);
    }
    return siz;
}

int get_root(int u, int fa, int tot, int &rt)
{
    if(st[u]) return 0;
    int siz = 1, ms = 0;
    for(auto i:e[u])
    {
        int v = i.v;
        if(v == fa) continue;
        int t = get_root(v, u, tot, rt);
        ms = max(ms, t);
        siz += t;
    }
    ms = max(ms, tot - siz);
    if(ms <= tot / 2) rt = u;
    return siz;
}

void get_dis(int u, int fa, int dis, int &qt)
{
    if(st[u] || dis > 1e7) return;
    q[++ qt] = dis;
    for(auto i:e[u])
    {
        int v = i.v, w = i.w;
        if(v == fa) continue;
        get_dis(v, u, dis + w, qt);
    }
}

void solve(int d[], int len, int f)
{
    cout << len <<endl;
    for(int i = 1;i <= len;i ++)
        for(int j = 1;j <= len;j ++)
            if(i != j && d[i] + d[j] <= 1e7)
            {
                ans[d[i] + d[j]] += f;
            }
}

void calc(int u)
{
    if(st[u]) return;
    st[u] = true;
    get_root(u, 0, get_siz(u, 0), u);
    int pt = 0;
    for(auto i:e[u])
    {
        int v = i.v, w = i.w;
        int qt = 0;
        get_dis(v, u, w, qt);
        solve(q, qt, -1);
        for(int i = 1;i <= qt;i ++)
            p[++ pt] = q[i];
    }
    solve(p, pt, 1);
    for(auto i:e[u])
    {
        int v = i.v;
        calc(v);
    }
}

int main()              //主函数
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 1;i < n;i ++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back(edge(v, w));
        e[v].push_back(edge(u, w));
    }
    calc(1);
    while(m --)
    {
        int k;
        cin >> k;
        if(ans[k]) cout << "AYE\n";
        else cout << "NYA\n";
    }
    return 0;
}

by _maojun__ @ 2023-02-03 13:38:52

solve 的复杂度假了吧/qd


|