寒冰大大 @ 2020-01-14 10:27:10
今天写博客的时候发现求重心部分和其他不一样，然后注释掉了只能跑60分，但是我这种方法显然错误，因为它并不会求出后面的重心（然而数据过水A了，还跑得和题解差不多），求大佬帮忙康康
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
struct edge{
int next,to,dis;
}e[20020];
int head[20020],size,tmp[10001000],judge[10001000];
int k,n,m;
int sz[20020],rt=1;
int maxp[20020],fw[20020],dis[20020];
int que[200200];
int yns[200200],sum;
int q[200200],vis[200200];
inline void addedge(int next,int to,int dis)
{
e[++size].to=to;
e[size].next=head[next];
e[size].dis=dis;
head[next]=size;
}
inline void getzx(int t,int fat)
{
sz[t]=1;
maxp[t]=1;
int i,j;
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
if(j==fat||fw[j]) continue;
fw[j]=1; //就是这个地方，理论上后来被一次求重心在根节点就会被continue
getzx(j,t);
sz[t]+=sz[j];
maxp[t]=max(maxp[t],sz[j]);
}
maxp[t]=max(maxp[t],sum-sz[t]);
if(maxp[t]<maxp[rt]) rt=t;
return ;
}
inline void getdis(int t,int fat)
{
tmp[++tmp[0]]=dis[t];
int i,j,k;
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
k=e[i].dis;
if(j==fat||vis[j]) continue;
dis[j]=dis[t]+k;
getdis(j,t);
}
}
inline void calc(int t)
{
int p=0;
int i,j,k,l;
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
if(vis[j]) continue;
tmp[0]=0;
dis[j]=e[i].dis;
getdis(j,t);
for(k=tmp[0];k;k--)
for(l=1;l<=m;l++) if(que[l]>=tmp[k]) yns[l]|=judge[que[l]-tmp[k]];
for(k=tmp[0];k;k--) q[++p]=tmp[k],judge[tmp[k]]=1;
}
for(i=1;i<=p;i++) judge[q[i]]=0;
}
inline void slove(int t)
{
vis[t]=judge[0]=1;calc(t);
int i,j;
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
if(vis[j]) continue;
rt=0,sum=sz[j],maxp[rt]=0x3f3f3f3f;
getzx(j,0); slove(j);
}
}
int main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>n>>m;
int t1,t2,t3;
sum=n;
for(i=1;i<n;i++) cin>>t1>>t2>>t3,addedge(t1,t2,t3),addedge(t2,t1,t3);
for(i=1;i<=m;i++) cin>>que[i];
getzx(1,0);
slove(rt);
for(i=1;i<=m;i++)
{
if(yns[i]) cout<<"AYE"<<endl;
else cout<<"NAY"<<endl;
}
return 0;
}by 寒冰大大 @ 2020-01-14 10:27:47
打错了：理论上后来每一次
by Rogers_wang @ 2020-01-14 10:28:50
...
by lemir3 @ 2020-01-14 10:39:10
阿了
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
struct edge{
int next,to,dis;
}e[20020];
int head[20020],size,tmp[10001000],judge[10001000];
int k,n,m;
int sz[20020],rt=1;
int maxp[20020],fw[20020],dis[20020];
int que[200200];
int yns[200200],sum;
int q[200200],vis[200200];
inline void addedge(int next,int to,int dis)
{
e[++size].to=to;
e[size].next=head[next];
e[size].dis=dis;
head[next]=size;
}
inline void getzx(int t,int fat)
{
sz[t]=1;
maxp[t]=0;
int i,j;
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
if(j==fat||vis[j]) continue;
// fw[j]=1; //就是这个地方，理论上后来被一次求重心在根节点就会被continue
getzx(j,t);
sz[t]+=sz[j];
maxp[t]=max(maxp[t],sz[j]);
}
maxp[t]=max(maxp[t],sum-sz[t]);
if(maxp[t]<maxp[rt]) rt=t;
return ;
}
inline void getdis(int t,int fat)
{
tmp[++tmp[0]]=dis[t];
int i,j,k;
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
k=e[i].dis;
if(j==fat||vis[j]) continue;
dis[j]=dis[t]+k;
getdis(j,t);
}
}
inline void calc(int t)
{
int p=0;
int i,j,k,l;
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
if(vis[j]) continue;
tmp[0]=0;
dis[j]=e[i].dis;
getdis(j,t);
for(k=tmp[0];k;k--)
for(l=1;l<=m;l++) if(que[l]>=tmp[k]) yns[l]|=judge[que[l]-tmp[k]];
for(k=tmp[0];k;k--) q[++p]=tmp[k],judge[tmp[k]]=1;
}
for(i=1;i<=p;i++) judge[q[i]]=0;
}
inline void slove(int t)
{
vis[t]=judge[0]=1;calc(t);
int i,j;
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
if(vis[j]) continue;
rt=0,sum=sz[j],maxp[rt]=0x3f3f3f3f;
getzx(j,0); slove(rt);
}
}
int main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>n>>m;
int t1,t2,t3;
maxp[rt]=sum=n;
for(i=1;i<n;i++) cin>>t1>>t2>>t3,addedge(t1,t2,t3),addedge(t2,t1,t3);
for(i=1;i<=m;i++) cin>>que[i];
getzx(1,0);
slove(rt);
for(i=1;i<=m;i++)
{
if(yns[i]) cout<<"AYE"<<endl;
else cout<<"NAY"<<endl;
}
return 0;
}by 小元勋 @ 2020-01-14 10:44:38
％％％％％％％％
by installb @ 2020-01-14 10:45:57
4178
by starseven @ 2020-01-14 11:09:52
Orz
(wowowow)
by 辰星凌 @ 2020-01-14 11:38:10
Orz淀粉质巨捞
by 寒冰大大 @ 2020-01-14 16:02:45
什么意思啊，还没有我后面打的正解快