《本题不卡常》

lqyc @ 2021-07-22 20:11:48

by lqyc @ 2021-07-22 20:12:01

#include<bits/stdc++.h>
using namespace std;
struct apple
{
    int dep,sy;
    bool operator<(const apple &other)const
    {
        return sy<other.sy;
    }
}e[10005];
int K,tot,q[10005],sy[10005],vist[10005],sz[10005],dep[10005];
int mp[10000005];
vector<pair<int,int> >g[10005];
void dfs(int x,int la)
{
    q[++tot]=x;
    sz[x]=1;
    for(int i=0;i<g[x].size();i++)
    {
        int cu=g[x][i].first,c2=g[x][i].second;
        if(cu==la||vist[cu])continue;
        dfs(cu,x);
        sz[x]+=sz[cu];
    }
}
void dfss(int x,int la,int l)
{
    sy[x]=l;
    for(int i=0;i<g[x].size();i++)
    {
        int cu=g[x][i].first,c2=g[x][i].second;
        if(cu==la||vist[cu])continue;
        dep[cu]=dep[x]+c2;
        dfss(cu,x,l);
    }
}
int merg(int x)
{
    tot=0;
    dfs(x,0);
    if(sz[x]==1)
    {
        vist[x]=1;
        return 0;
    }
    int aaa=INT_MAX,w;
    for(int i=1;i<=tot;i++)
    {
        int mx=sz[x]-sz[q[i]];
        for(int j=0;j<g[q[i]].size();j++)
        {
            int cu=g[q[i]][j].first,c2=g[q[i]][j].second;
            if(vist[cu]||sz[cu]>sz[q[i]])continue;
            mx=max(mx,sz[cu]);
        }
        if(aaa>mx)aaa=mx,w=q[i];
    }
    vist[w]=1,sy[w]=-1,dep[w]=0;
    for(int i=0;i<g[w].size();i++)
    {
        int cu=g[w][i].first,c2=g[w][i].second;
        if(vist[cu])continue;
        dep[cu]=c2;
        dfss(cu,w,i);
    }
    for(int i=1;i<=tot;i++)e[i].sy=sy[q[i]],e[i].dep=dep[q[i]];
    sort(e+1,e+tot+1);
    int ans=0;
    for(int i=1;i<=tot;)
    {
        int wz=i;
        while(wz<tot&&e[wz+1].sy==e[wz].sy)wz++;
        for(int j=i;j<=wz;j++)if(e[j].dep<=K)ans+=mp[e[j].dep];
        for(int j=i;j<=wz;j++)if(K>=e[j].dep)mp[K-e[j].dep]++;
        i=wz+1;
    }
    for(int i=1;i<=tot;i++)if(K>=e[i].dep)mp[K-e[i].dep]=0;
    if(ans)return 1;
    for(int i=0;i<g[w].size();i++)
    {
        int cu=g[w][i].first;
        if(vist[cu])continue;
        ans+=merg(cu);
        if(ans)return 1;
    }
    return ans;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        g[u].push_back(make_pair(v,w));
        g[v].push_back(make_pair(u,w));
    }
    while(m--)
    {
        scanf("%d",&K);
        for(int i=1;i<=n;i++)vist[i]=0;
        if(merg(1))printf("AYE\n");
        else printf("NAY\n");
    }
    return 0;
}

by cyffff @ 2021-07-22 20:40:21

确实不卡常，应该是你假了