boatherds 2s 64M by czy
求一颗树上距离为K的点对是否存在
输入数据
n,m
接下来n-1条边a,b,c描述a到b有一条长度为c的路径
接下来m行每行询问一个K
输出数据
对于每个K每行输出一个答案,存在输出“AYE”,否则输出”NYE”(不包含引号)
数据范围
对于30%的数据n<=100
对于60%的数据n<=1000,m<=50
对于100%的数据n<=10000,m<=100,c<=1000,K<=10000000
点分治。
但是每次询问会超时,所以需要离线。
就把K都存起来,每次询问的时候都for一遍K。
代码:
// #pragma comment(linker,"/STACK:102400000,102400000")
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; const int N=;
int n,m,sl,kl,tl,vl,len,first[N],mark[N],s[N],t[N],d[N],size[N],K[N],ans[N];//,v[N];
bool v[];
struct node{
int x,y,d,next;
}a[*N]; bool cmp(int x,int y){return x<y;} void ins(int x,int y,int d)
{
a[++len].x=x;a[len].y=y;a[len].d=d;
a[len].next=first[x];first[x]=len;
} void find_root(int x,int fa,int tot,int &root)
{
size[x]=;
bool bk=;
for(int i=first[x];i;i=a[i].next)
{
int y=a[i].y;
if(y==fa || mark[y]) continue;
find_root(y,x,tot,root);
size[x]+=size[y];
if(*size[y]>tot) bk=;
}
if(bk && *(tot-size[x])<=tot) root=x;
} void DFS(int x,int fa)
{
for(int i=;i<=kl;i++)
{
if(K[i]>=d[x] && v[K[i]-d[x]]) ans[i]=;
}
// if(ans==1) return ;
t[++tl]=d[x];
size[x]=;
for(int i=first[x];i;i=a[i].next)
{
int y=a[i].y;
if(y==fa || mark[y]) continue;
d[y]=d[x]+a[i].d;
DFS(y,x);
size[x]+=size[y];
}
} void dfs(int x,int tot)
{
find_root(x,,tot,x);
v[]=;sl=;//ssl=0;
// s[++sl]=x;
mark[x]=;
for(int i=first[x];i;i=a[i].next)
{
int y=a[i].y;
if(mark[y]) continue;
tl=;d[y]=a[i].d;
DFS(y,x);
// if(ans==1) break;
for(int j=;j<=tl;j++) v[t[j]]=,s[++sl]=t[j];
}
for(int i=;i<=sl;i++) v[s[i]]=;
// if(ans==1) return ;
for(int i=first[x];i;i=a[i].next)
{
int y=a[i].y;
if(mark[y]) continue;
dfs(y,size[y]);
}
} int main()
{
// freopen("a.in","r",stdin);
freopen("boatherds.in","r",stdin);
freopen("boatherds.out","w",stdout);
scanf("%d%d",&n,&kl);
len=;
memset(v,,sizeof(v));
memset(first,,sizeof(first));
for(int i=;i<n;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);
ins(y,x,c);
}
for(int i=;i<=kl;i++) scanf("%d",&K[i]);
memset(ans,,sizeof(ans));
dfs(,n);
for(int i=;i<=kl;i++)
{
if(ans[i]) printf("AYE\n");
else printf("NAY\n");
}
return ;
}