求调

P3806 【模板】点分治 1

alpharchmage @ 2024-07-16 09:52:35

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n = 0 , m = 0 , cnt = 0 , root_now = 0 , sum_now = 0 , tot = 0 , tmp = 0;
array<int , 2000100> head , dis , vis , query , sizes , dp , solved , exist , del;
bitset<100000100> judged;
struct Node{
    int to;
    int val;
    int nxt;
};
array<Node , 2000100> edge;
void new_line(int a , int b , int c)
{
    edge.at(++ cnt).to = b;
    edge.at(cnt).nxt = head.at(a);
    edge.at(cnt).val = c;
    head.at(a) = cnt;
    return;
}
void get_root(int x , int fa)
{
    sizes.at(x) = 1;
    dp.at(x) = 0;
    for(int e = head.at(x);e;e = edge.at(e).nxt)
    {
        int to = edge.at(e).to;
        if(to != fa && !vis.at(to))
        {
            get_root(to , x);
            sizes.at(x) += sizes.at(to); 
            dp.at(x) = max(dp.at(x) , sizes.at(to));
        }
    }
    dp.at(x) = max(sizes.at(x) , sum_now - sizes.at(x));
    if(dp.at(x) < dp.at(root_now))
    {
        root_now = x;
    }
    return;
}
void init(int x , int fa)
{
    exist.at(++ tmp) = dis.at(x);
    for(int e = head.at(x);e;e = edge.at(e).nxt)
    {
        int to = edge.at(e).to;
        if(to != fa && !vis.at(to))
        {
            dis.at(to) = dis.at(x) + edge.at(e).val;
            init(to , x);
        } 
    }
}
void update(int x)
{
    tot = 0;
    for(int e = head.at(x);e;e = edge.at(e).nxt)
    {
        int to = edge.at(e).to;
        if(vis.at(to))
        {
            continue;
        }
        tmp = 0;
        dis.at(to) = edge.at(e).val;
        init(to , x);
        for(int i = tmp;i >= 1;-- i)
        {
            for(int k = 1;k <= m;++ k)
            {
                if(query.at(k) >= exist.at(i))
                {
                    solved.at(k) |= judged.test(query.at(k) - exist.at(i));
                }
            }
        }
        for(int i = tmp;i >= 1;-- i)
        {
            del.at(++ tot) = exist.at(i);
            judged.set(exist.at(i)) = true;
        }
    }
    for(int i = 1;i <= tot;++ i)
    {
        judged.reset(del.at(i)) = false;
    }
}
void dfs(int x)
{
    vis.at(x) = true;
    judged.set(0);
    update(x);
    for(int e = head.at(e);e;e = edge.at(e).nxt)
    {
        int to = edge.at(e).to;
        if(!vis.at(to))
        {
            root_now = 0;
            dp.at(root_now) = INT_MAX;
            sum_now = sizes.at(x);
            get_root(to , -1);
            dfs(root_now);
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    for(int i = 1;i <= (n - 1);++ i)
    {
        int x = 0 , y = 0 , k = 0;
        cin >> x >> y >> k;
        new_line(x , y , k);
        new_line(y , x , k);
    }
    for(int i = 1;i <= m;++ i)
    {
        cin >> query.at(i);
    }
    dp.at(0) = INT_MAX;
    sum_now = n;
    get_root(1 , 0);
    dfs(root_now);
    for(int i = 1;i <= m;++ i)
    {
        if(solved.at(i))
        {
            cout << "AYE" << endl;
        }
        else
        {
            cout << "NAY" << endl;
        }
    }
    return 0;
}

by _Kamisato_Ayaka_ @ 2024-07-16 10:10:48

Alpha!


|