F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 1316 >> 这题写hash可以暴力卡过(在线)
lahlah @ 2018-08-07 16:47:44
[ Quote ] [ Edit ] [ Delete ] 1#
#include<bits/stdc++.h>
#pragma GCC optimize (2)
#define ll long long
#define lowbit(x) x & -x
using namespace std;
const int N =20005;
const int mod =9999991;
struct A{
int v,next,c;
}e[N];
int n,m,sum[N],K,eid,size[N],msize[N],vis[N],p[N],q[N],l,r,ff;
long long dep[N];
int po[N*500],poo[N*500],pg[N*500],tot,next[N*500];
void init(){
memset(p,-1,sizeof(p));
eid=0;
}
void add(int u,int v,int c){
eid++;
e[eid].v=v;
e[eid].c=c;
e[eid].next=p[u];
p[u]=eid;
}
void dfs(int x){
q[++r]=x;
vis[x]=1;size[x]=1;msize[x]=1;
for(int i=p[x];i+1;i=e[i].next){
int v=e[i].v;
int c=e[i].c;
if(vis[v]) continue;
dep[v]=dep[x]+c;
dfs(v);
size[x]+=size[v];
msize[x]=max(msize[x],size[v]);
}
vis[x]=0;
}
bool cmp(int x,int y){
return dep[x]<dep[y];
}
int ha(int x){
int t=x%mod;
int pos=poo[t];
if(!pos) {tot++;poo[t]=tot;pg[tot]=x;next[tot]=0; return tot;}
else{
while(pos){
if(pg[pos]==x) return pos;
pos=next[pos];
}
tot++;
next[tot]=poo[t];
pg[tot]=x;
poo[t]=tot;// printf("%d\n",tot);
return tot;
}
}
int calc(int x,int y){
if(ff) return ff;
int ans=0;
for(int i=x;i<=y;i++) po[ha(dep[q[i]])] ++;
for(int i=x;i<=y;i++){
if(dep[q[i]]>K) continue;
if(po[ha(K-dep[q[i]])]) {ans+=po[ha(K-dep[q[i]])];}
}
for(int i=x;i<=y;i++) po[ha(dep[q[i]])] --;
return ans;
}
void work(int x){
if(ff) return;
l=1,r=0;
dfs(x);
int top=size[x],mi=msize[x];
for(int i=1;i<=r;i++){
int v=q[i];
if(max(size[v],top-size[v])<mi) mi=max(size[v],top-size[v]),x=v;
}
vis[x]=1;
int ans=0;
l=1;r=0;
for(int i=p[x];i+1;i=e[i].next){
int v=e[i].v;
int c=e[i].c;
if(vis[v]) continue;
dep[v]=c; dfs(v);
ans-=calc(l,r);
l=r+1;
}
dep[x]=0;q[++r]=x;
ans+=calc(1,r);
if(ans) {ff=1;return;}
for(int i=p[x];i+1;i=e[i].next){
int v=e[i].v;
if(vis[v]) continue;
work(v);
}
}

int main(){
init();
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
add(u,v,c);
add(v,u,c);
}
for(;m--;){
for(int i=1;i<N;i++) vis[i]=0,sum[i]=0,size[i]=0,dep[i]=0;
scanf("%d",&K);
ff=0;
work(1);
if(K==0) {printf("Yes\n");continue;}
if(ff) printf("Yes\n");
else printf("No\n");
}
return 0;
}
[Top] [Previous Page] [Next Page]

HOME Back