a_sad_soul @ 2023-03-19 17:30:34
点分治多分了但是找不到为什么多分(
#include<bits/stdc++.h>
#define MAXN 100005
#define MAXXN 500000005
using namespace std;
struct node {
int to,val;
node *next;
}*tmp,*head[MAXN];
int del[MAXN],n,m,query[MAXN],size[MAXN],dist[MAXN],dis[MAXN];
int root,tot;
bool vis[MAXN],judge[MAXXN],ans[MAXN],S;
void add(int u,int v,int w)
{
tmp=new node;
tmp->to=v;
tmp->val=w;
tmp->next=head[u];
head[u]=tmp;
}
int mx[MAXN];
int to1,to2,to3;
void getroot(int u,int fa)
{++to1;
size[u]=1;
mx[u]=0;
for(node *i=head[u];i!=NULL;i=i->next)
{
int v=i->to,val=i->val;
if(v==fa||vis[v])continue;
getroot(v,u);
size[u]+=size[v];
mx[u]=max(size[v],mx[u]);
}
mx[u]=max(mx[u],S-size[u]);
if(mx[u]<size[root])
root=u;
}
void getdis(int u,int fa)
{++to2;
dis[++dis[0]]=dist[u];
for(node *i=head[u];i!=NULL;i=i->next)
{
int v=i->to;
if(v==fa||vis[v])continue;
dist[v]=dist[u]+i->val;
getdis(v,u);
}
}
void solve(int u)
{
del[0]=0;
for(node *i=head[u];i!=NULL;i=i->next)
{
int v=i->to;
//cout<<v<<" "<<vis[v]<<endl;
if(vis[v])continue;
dis[0]=0;
dist[v]=i->val;
getdis(v,u);
//cout<<dis[0]<<endl;
for(int j=1;j<=dis[0];++j)
{
for(int k=1;k<=m;++k)
{
if(dis[j]<=query[k])
ans[k]|=judge[query[k]-dis[j]];
}//cout<<dis[j]<<endl;
}
for(int j=1;j<=dis[0];++j)judge[dis[j]]=1,del[++del[0]]=dis[j];
//for(int i=1;j<=dis[0];++)
}
for(int i=1;i<=del[0];++i)
{
judge[del[i]]=0;
}
}
void divide(int u)
{++to3;
vis[u]=1;
//cout<<"k"<<endl;
judge[0]=1;
solve(u);
for(node *i=head[u];i!=NULL;i=i->next)
{
int v=i->to;
if(vis[v])continue;
S=size[v];
mx[0]=n;
root=0;
getroot(v,0);
divide(root);
}
}
int main()
{
//judge[0]=1;
freopen("1.in","r",stdin);
freopen("out.txt","w",stdout);
size[0]=1451041910;
cin>>n>>m;
for(int i=1;i<n;++i)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w),add(v,u,w);
}
for(int i=1;i<=m;++i)
scanf("%d",&query[i]);
S=n;
mx[0]=n;
root=0;
getroot(1,0);
//for(int i=1;i<=n;++i)cout<<vis[i];
//cout<<endl;
divide(root);
for(int i=1;i<=m;++i)
if(ans[i])printf("AYE\n");
else printf("NAY\n");
cout<<to1<<endl<<to2<<endl<<to3;
return 0;
}
by zjy2008 @ 2023-03-19 17:48:16
修改
if(mx[u]<size[root])
root=u;
为
if(mx[u]<mx[root])
root=u;
这样会导致重心寻找错误,时间复杂度退化
by a_sad_soul @ 2023-03-20 22:51:41
@OIdrearmer_Z 谢谢大佬,一直没看到555
by a_sad_soul @ 2023-03-20 22:55:04
@OIdrearmer_Z 改了,但是好像没有什么用捏
by zjy2008 @ 2023-03-21 08:24:21
@a_sad_soul 抱歉,现在才看到
bool vis[MAXN],judge[MAXXN],ans[MAXN],S;
by a_sad_soul @ 2023-03-21 13:19:13
@OIdrearmer_Z wc什么低级错误,谢谢大佬%%%