点分治-luogu 3806
26588 ワード
タイトルリンク
luogu3806
構想
この問題は点分治のテンプレートの問題で、点分治は1本の木の上の分治です.詳しい教程の上でB駅はAgOHの生放送を見て、とても大きい人の分かち合う点に感謝して教程を分けます-作者:AgOH
コード実装
luogu3806
構想
この問題は点分治のテンプレートの問題で、点分治は1本の木の上の分治です.詳しい教程の上でB駅はAgOHの生放送を見て、とても大きい人の分かち合う点に感謝して教程を分けます-作者:AgOH
コード実装
#include
using namespace std;
#define ll long long
const int N = 1e4+10;
const int NN = 1e7+10;
struct edge{
int v,dis,nex;
}edges[N<<1];
int head[N<<1],edgenum,sum,rt,n,m,cnt;
int maxp[N],siz[N],dis[N],q[N/10],tmp[N<<1];
bool ans[NN],judge[NN],vis[N];
void add(int u,int v,int dis){
edges[edgenum].nex=head[u];
edges[edgenum].v=v;
edges[edgenum].dis=dis;
head[u]=edgenum++;
}
void getrt(int u,int fa){
siz[u]=1,maxp[u]=0;
for(int i=head[u];~i;i=edges[i].nex){
int v = edges[i].v;
if(vis[v]||v==fa)continue;
getrt(v,u);
siz[u]+=siz[v];
if(maxp[u]<siz[v])maxp[u]=siz[v];
}
maxp[u]=max(maxp[u],sum-siz[u]);
if(maxp[u]<maxp[rt])rt=u;
}
void getdis(int u,int f){
tmp[cnt++]=dis[u];
for(int i=head[u];~i;i=edges[i].nex){
int v = edges[i].v;
if(v==f||vis[v])continue;
dis[v]=dis[u]+edges[i].dis;
getdis(v,u);
}
}
void solve(int u){
queue<int>que;
for(int i=head[u];~i;i=edges[i].nex){
int v = edges[i].v;
if(vis[v])continue;
cnt = 0;
dis[v]=edges[i].dis;
getdis(v,u);
for(int j=0;j<cnt;j++){
for(int k=0;k<m;k++){
if(q[k]>=tmp[j]){
ans[k]|=judge[q[k]-tmp[j]];
}
}
}
for(int j=0;j<cnt;j++){
que.push(tmp[j]);
judge[tmp[j]]=1;
}
}
while (!que.empty()){
judge[que.front()]=false;
que.pop();
}
}
void divide(int u){
vis[u]=judge[0]=1;
solve(u);//
for(int i=head[u];~i;i=edges[i].nex){
int v = edges[i].v;
if(vis[v])continue;
maxp[rt=0]=sum=siz[v];
getrt(v,0);
// size ,
getrt(rt,0);
divide(rt);
}
}
int main(){
memset(head,-1,sizeof(head));
scanf("%d %d",&n,&m);
for(int i=0;i<n-1;i++){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
for(int i=0;i<m;i++)scanf("%d",&q[i]);
maxp[0]=sum=n;
getrt(1,0);
getrt(rt,0);
divide(rt);
for(int i=0;i<m;i++){
if(ans[i])printf("AYE
");
else printf("NAY
");
}
return 0;
}