[bzoj1316] 树上的询问

时间：2024-04-08 17:03:32

　　裸的点分治。。

　　及时把已经确定的询问清掉就能快不少。时间复杂度O(nlogn*p)

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn=;

 struct zs{int len,id;bool done;}q[];

 struct zs1{int too,pre,dis;}e[maxn<<];int tot,last[maxn];

 int st[maxn],top,pre,sz[maxn],mx[maxn],POI,dis[maxn];

 bool gg[],can[],del[maxn];

 int i,j,k,n,m,rt,mm;

 int ra;char rx;

 inline int read(){

     rx=getchar(),ra=;

     while(rx<''||rx>'')rx=getchar();

     while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;

 }

 inline int max(int a,int b){return a>b?a:b;}

 void getrt(int x,int fa){

     sz[x]=,mx[x]=;

     for(int i=last[x];i;i=e[i].pre)if(!del[e[i].too]&&e[i].too!=fa)

         getrt(e[i].too,x),sz[x]+=sz[e[i].too],mx[x]=max(mx[x],sz[e[i].too]);

     mx[x]=max(mx[x],POI-sz[x]);

     if(mx[x]<mx[rt])rt=x;

 }

 void getpoi(int x,int fa){

     st[++top]=dis[x];

     for(int i=last[x];i;i=e[i].pre)if(!del[e[i].too]&&e[i].too!=fa)

         dis[e[i].too]=dis[x]+e[i].dis,getpoi(e[i].too,x);

 }

 inline void updQ(){

     mm=m;m=;

     for(int i=;i<=mm;i++)if(!q[i].done)q[++m]=q[i];

 }

 void work(int x){

     int i,j,k;bool flag=;

     rt=,getrt(x,);

     can[]=;pre=;

     for(i=last[rt];i;i=e[i].pre)if(!del[e[i].too]){

         dis[e[i].too]=e[i].dis,getpoi(e[i].too,rt);

         for(j=pre;j<=top;j++)

             for(k=;k<=m&&q[k].len>=st[j];k++)if(can[q[k].len-st[j]])q[k].done=,flag=;

         while(pre<=top)

             if(st[pre]<=q[].len)

                 can[st[pre++]]=;

             else pre++;

     }

     if(flag)updQ();

     if(!m)return;

     while(top)

         if(st[top]<=)can[st[top--]]=;else top--;

     del[rt]=;

     for(i=last[rt];i;i=e[i].pre)if(!del[e[i].too])POI=sz[e[i].too],work(e[i].too);

 }

 inline void insert(int a,int b,int c){

     e[++tot].too=b,e[tot].dis=c,e[tot].pre=last[a],last[a]=tot;

     e[++tot].too=a,e[tot].dis=c,e[tot].pre=last[b],last[b]=tot;

 }

 bool cmp(zs a,zs b){return a.len>b.len;}

 int main(){mx[]=1e9;

     n=read(),m=read();int m1=m;

     for(i=;i<n;i++)j=read(),k=read(),insert(j,k,read());

     for(i=;i<=m;i++)q[i].len=read(),q[i].id=i;

     sort(q+,q++m,cmp);

     while(m&&q[m].len==)q[m].done=,m--;

     POI=n,work();

     for(i=;i<=m;i++)gg[q[i].id]=;

     for(i=;i<=m1;i++)puts(gg[i]?"No":"Yes");

     return ;

 }

相关文章