求助点分治

Moeebius @ 2022-08-19 21:01:16

#include<bits/stdc++.h>
using namespace std;

#define il inline
#define mkp make_pair
#define pii pair<int,int>
#define lll __int128
#define ll long long
#define For(i,j,k) for(int i=(j); i<=(k); ++i)
#define ForDown(i,j,k) for(int i=(j); i>=(k); --i)
#define pb push_back
#define init(filename) freopen(filename ".in" ,"r",stdin);freopen(filename ".out" ,"w",stdout)
template<typename T> 
il void read(T &x){ x=0;int f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=f;}
template<typename T, typename ... Args>
il void read(T &x, Args &... y){ read(x);read(y...); }

int n,m,root;
vector<pii> T[10001];
struct Query
{
    int k;
    bool ok;
}Q[101];

bool vis[10001];
int sz[10001],maxp[10001],dis[10001],sub[10001],a[10001],tot;

void getRoot(int x, int fa, int sum)
{
    // cerr<<x<<' '<<fa<<' '<<sum<<endl;
    sz[x]=1,maxp[x]=0;
    for(pii ed: T[x])
    {
        int v=ed.first;
        if(v==fa || vis[v]) continue;
        getRoot(v,x,sum);
        sz[x]+=sz[v];
        maxp[x]=max(maxp[x],sz[v]);
    }
    maxp[x]=max(maxp[x],sum-sz[x]);
    if(!root || maxp[x]<maxp[root]) root=x;
}
void getDis(int x, int fa, int w, int rt)
{
    ++tot;
    a[tot]=x,dis[tot]=w,sub[tot]=rt;
    for(pii ed: T[x])
    {
        int v=ed.first,dw=ed.second;
        if(v==fa || vis[v]) continue;
        getDis(v,x,w+dw,rt);
    }
}
il bool __cmp_node(const int &a, const int &b){ return dis[a]<dis[b]; }
void cal(int x)
{
    // cerr<<x<<endl;
    tot=1;
    a[tot]=x,dis[tot]=0,sub[tot]=x;
    for(pii ed: T[x])
    {
        int v=ed.first,w=ed.second;
        if(vis[v]) continue;
        getDis(v,x,w,v);
    }
    sort(a+1,a+tot+1,__cmp_node);
    For(i,1,m)
    {
        int l=1,r=tot;
        if(Q[i].ok) continue;
        while(l<r)
        {
            if(dis[a[l]]+dis[a[r]]<Q[i].k) ++l;
            else if(dis[a[l]]+dis[a[r]]>Q[i].k) --r;
            else if(sub[a[l]]==sub[a[r]])
            {
                if(dis[a[r-1]]==dis[a[r]]) --r;
                else ++l;
            }
            else
            {
                Q[i].ok=1;
                break;
            }
        }
    }
}
void solve(int x)
{
    // cout<<x<<endl;
    vis[x]=1;
    cal(x);
    for(pii ed: T[x])
    {
        int v=ed.first;
        if(vis[v]) continue;
        root=0;
        getRoot(v,0,sz[v]);
        solve(root);
    }
}

string ans[]={"AYE","NAY"};

signed main()
{
    read(n,m);
    For(i,1,n-1)
    {
        int u,v,w;
        read(u,v,w);
        T[u].pb(mkp(v,w));T[v].pb(mkp(u,w));
    }
    For(i,1,m)
    {
        read(Q[i].k);
        Q[i].ok=!Q[i].k?1:0;
    }
    root=0;
    maxp[0]=n;
    getRoot(1,0,n);
    solve(root);
    For(i,1,m) printf("%s\n",ans[Q[i].ok^1].c_str());
    return 0;
}

by junxis @ 2022-10-09 19:54:07

@Xiaohuba

#include<bits/stdc++.h>
using namespace std;

#define il inline
#define mkp make_pair
#define pii pair<int,int>
#define lll __int128
#define ll long long
#define For(i,j,k) for(int i=(j); i<=(k); ++i)
#define ForDown(i,j,k) for(int i=(j); i>=(k); --i)
#define pb push_back
#define init(filename) freopen(filename ".in" ,"r",stdin);freopen(filename ".out" ,"w",stdout)
template<typename T> 
il void read(T &x){ x=0;int f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=f;}
template<typename T, typename ... Args>
il void read(T &x, Args &... y){ read(x);read(y...); }

int n,m,root;
vector<pii> T[10001];
struct Query
{
    int k;
    bool ok;
}Q[101];

bool vis[10001];
int sz[10001],maxp[10001],dis[10001],sub[10001],a[10001],tot;

void getRoot(int x, int fa, int sum)
{
    // cerr<<x<<' '<<fa<<' '<<sum<<endl;
    sz[x]=1,maxp[x]=0;
    for(pii ed: T[x])
    {
        int v=ed.first;
        if(v==fa || vis[v]) continue;
        getRoot(v,x,sum);
        sz[x]+=sz[v];
        maxp[x]=max(maxp[x],sz[v]);
    }
    maxp[x]=max(maxp[x],sum-sz[x]);
    if(!root || maxp[x]<maxp[root]) root=x;
}
void getDis(int x, int fa, int w, int rt)
{
    ++tot;
    a[tot]=x,dis[x]=w,sub[x]=rt; // !!!!!!!!!!!
    for(pii ed: T[x])
    {
        int v=ed.first,dw=ed.second;
        if(v==fa || vis[v]) continue;
        getDis(v,x,w+dw,rt);
    }
}
il bool __cmp_node(const int &a, const int &b){ return dis[a]<dis[b]; }
void cal(int x)
{
    // cerr<<x<<endl;
    tot=1;
    a[tot]=x,dis[x]=0,sub[x]=x; // !!!!!!!!!!!
    for(pii ed: T[x])
    {
        int v=ed.first,w=ed.second;
        if(vis[v]) continue;
        getDis(v,x,w,v);
    }
    sort(a+1,a+tot+1,__cmp_node);
    For(i,1,m)
    {
        int l=1,r=tot;
        if(Q[i].ok) continue;
        while(l<r)
        {
            if(dis[a[l]]+dis[a[r]]<Q[i].k) ++l;
            else if(dis[a[l]]+dis[a[r]]>Q[i].k) --r;
            else if(sub[a[l]]==sub[a[r]])
            {
                if(dis[a[r-1]]==dis[a[r]]) --r;
                else ++l;
            }
            else
            {
                Q[i].ok=1;
                break;
            }
        }
    }
}
void solve(int x)
{
    // cout<<x<<endl;
    vis[x]=1;
    cal(x);
    for(pii ed: T[x])
    {
        int v=ed.first;
        if(vis[v]) continue;
        root=0;
        getRoot(v,0,sz[v]);
        solve(root);
    }
}

string ans[]={"AYE","NAY"};

signed main()
{
    read(n,m);
    For(i,1,n-1)
    {
        int u,v,w;
        read(u,v,w);
        T[u].pb(mkp(v,w));T[v].pb(mkp(u,w));
    }
    For(i,1,m)
    {
        read(Q[i].k);
        Q[i].ok=!Q[i].k?1:0;
    }
    root=0;
    maxp[0]=n;
    getRoot(1,0,n);
    solve(root);
    For(i,1,m) printf("%s\n",ans[Q[i].ok^1].c_str());
    return 0;
}