点分治求助

P3806 【模板】点分治 1

清平乐 @ 2020-08-29 17:00:51

7#9一直T了,放在linux下大概要跑600ms,是什么地方写错了吗?

#include<stdio.h>
#include<bits/stdc++.h>
#define max(a,b) ((a)>(b)?(a):(b)) 
using namespace std;

const int INF=1e9,N=1e4+5,MAX=1e7+5;
int n,m,u,v,w,k,MaxSize,tot,root,tail,up;
int head[N],size[N],son[N],q[N],d[N],query[N],ans[N];
bool visit[N],task[N],judge[MAX];
struct edge{int v,w,next;}e[N<<1];

inline void add(int u,int v,int w)
{
    e[++k]=(edge){v,w,head[u]};
    head[u]=k;
}

void find(int u,int fa)
{
    size[u]=1,son[u]=0;
    for(register int i=head[u];i;i=e[i].next)
    {
        if(fa==e[i].v||visit[e[i].v]) continue;
        find(e[i].v,u);
        size[u]+=size[e[i].v];
        son[u]=max(son[u],size[e[i].v]);
    }
    son[u]=max(son[u],tot-size[u]);
    if(son[u]<MaxSize) MaxSize=son[u],root=u;
}

void getdis(int u,int fa)
{
    if(d[u]>up) return;
    q[++tail]=d[u];
    for(register int i=head[u];i;i=e[i].next)
    {
        if(e[i].v==fa||visit[e[i].v]) continue;
        d[e[i].v]=d[u]+e[i].w;
        getdis(e[i].v,u);
    }
}

inline void solve(int u)
{
    int cnt=0;
    for(register int i=head[u];i;i=e[i].next)
    {
        if(visit[e[i].v]) continue;
        tail=0,d[e[i].v]=e[i].w;
        getdis(e[i].v,u);
        for(register int j=tail;j;--j)
            for(register int k=1;k<=m;++k)
                if(query[k]>=q[j]) task[k]|=judge[query[k]-q[j]];
        for(register int j=tail;j;--j)
            ans[++cnt]=q[j],judge[q[j]]=true;
    }
    for(register int i=1;i<=cnt;++i)
        judge[ans[i]]=false;
}

void divide(int u)
{
    visit[u]=judge[0]=true;
    solve(u);
    for(register int i=head[u];i;i=e[i].next)
    {
        if(visit[e[i].v]) continue;
        MaxSize=INF,root=0;
        tot=size[e[i].v]>size[u]?tot-size[u]:size[e[i].v];
        find(e[i].v,0);
        divide(root);
    }
}

int main(void)
{
    scanf("%d%d",&n,&m);
    for(register int i=1;i<n;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w),add(v,u,w);
    }
    for(register int i=1;i<=m;++i)
    {
        scanf("%d",&query[i]);
        up=max(up,query[i]);
    }
    tot=n,MaxSize=INF;
    find(1,0);
    divide(root);
    for(register int i=1;i<=m;++i)
        puts(task[i]?"AYE":"NAY");
    return 0;
}

by 柳苏明 @ 2020-08-29 17:05:46

%%%TQL


by dottle @ 2020-08-29 17:21:57

tot=size[e[i].v]>size[u]?tot-size[u]:size[e[i].v];

这句话,循环开始前把tot存一下


|