help!不知为何全部RE

P3806 【模板】点分治 1

some_of_funny @ 2023-05-06 21:25:47

如题

#include<bits/stdc++.h>
#define maxn 10001
#define maxk 10000010
using namespace std;
vector<pair<int,int> >edge[maxn<<1];
bool vis[maxn];
int maxpt[maxn];
int siz[maxn];
int rt,rn;
bool judge[maxk];
int dis[maxn];
int tmp[maxn];
int q[maxn];
int n,m;
void getrt(int p,int fa)
{
    maxpt[p]=0;
    siz[p]=1;
    int l=edge[p].size(),v;
    for(int i=0;i<l;i++)
    {
        v=edge[p][i].first;
        if(v==fa||vis[v])
            continue;
        getrt(v,p);
        siz[p]+=siz[v];
        maxpt[p]=max(maxpt[p],siz[v]);
    }
    maxpt[p]=max(rn-siz[p],maxpt[p]);
    if(maxpt[p]<maxpt[rt])rt=p;
}
int cnt;
int getdis(int p,int fa)
{
    tmp[++cnt]=dis[p];
    int l=edge[p].size();
    for(int i=0;i<l;i++)
    {
        int v=edge[p][i].first;
        if(v==fa||vis[v])
            continue;
        dis[v]=dis[p]+edge[p][i].second;
        getdis(v,p);
    }
}
bool ans[maxn];
int solve(int u)
{
    queue<int>qu;
    int l=edge[u].size();
    for(int i=0;i<l;i++)
    {
        int v=edge[u][i].first;
        int w=edge[u][i].second;
        cnt=0;
        dis[v]=w;
        getdis(v,u);//处理以u为根节点的距离 
        for(int j=1;j<=cnt;j++)
            for(int k=1;k<=m;k++)
                if(q[k]>=tmp[j])
                    ans[k]|=judge[q[k]-tmp[j]];
        for(int j=1;j<=cnt;j++)
        {
            qu.push(tmp[j]);
            judge[tmp[j]]=true;
        }
    }
    while(!qu.empty())
    {
        judge[qu.front()]=false;
        qu.pop();
    }
}
void divide(int p)
{
    judge[0]=true;
    vis[p]=1;
    solve(p);
    int l=edge[p].size();
    for(int i=0;i<l;i++)
    {
        int v=edge[p][i].first;
        if(vis[v])
            continue;
        rt=0;
        maxpt[rt]=rn=siz[v]; 
        getrt(v,0);
        getrt(rt,0);
        divide(rt);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int u,v,w;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        edge[u].push_back(make_pair(v,w));
        edge[v].push_back(make_pair(u,w));
    }
    for(int i=1;i<=m;i++)
        scanf("%d",&q[i]);
    maxpt[0]=rn=n;
    getrt(1,0);
    getrt(rt,0);
    divide(rt);
    for(int i=1;i<=m;i++)
        if(ans[i])cout<<"AYE\n";
        else cout<<"NAY\n";
        //cout<<(ans[i]?"AYE":"NAY")<<"\n";
    return 0;
} 

by some_of_funny @ 2023-05-07 16:30:01

怎么沉了


|