zhoukangyang @ 2020-03-04 22:14:24
桶
#include<bits/stdc++.h>
using namespace std;
int kn,N,n,k[23333],u,v,q,siz[41111],rot,mas,fa[41111],mi[41111],paint[41111],deep[41111],color_id;
int head[41111],last[41111],ans[23333],stackk[41111],dfn;
struct node {
int to,next,val;
} s[233333];
void find_root(int x) {
siz[x]=1,mi[x]=0;
for(int i = head[x]; i != 0; i = s[i].next) {
if(s[i].to==fa[x]) continue;
if(paint[s[i].to]!=paint[x]) continue;
fa[s[i].to]=x;
find_root(s[i].to);
mi[x]=max(mi[x],siz[s[i].to]),siz[x]+=siz[s[i].to];
}
mi[x]=max(mi[x],N-siz[x]);
if(mas>mi[x]) mas=mi[x],rot=x;
}
void cz(int x) {
siz[x]=1;
for(int i = head[x]; i != 0; i = s[i].next) {
if(s[i].to==fa[x]) continue;
if(paint[s[i].to]!=paint[x]) continue;
fa[s[i].to]=x,cz(s[i].to),siz[x]+=siz[s[i].to];
}
}
void low(int x) {
for(int i = head[x]; i != 0; i = s[i].next) {
if(s[i].to==fa[x]) continue;
if(paint[s[i].to]!=paint[x]) continue;
deep[s[i].to]=deep[x]+s[i].val,fa[s[i].to]=x,low(s[i].to),siz[x]+=siz[s[i].to];
}
++dfn,stackk[dfn]=x,paint[x]=color_id;
}
void dfs(int x) {
int ma[11111111];
if(N==1) return;
int yousb[41111],sz[41111],lowbit=0;
fa[x]=rot=0,mas=1e9,find_root(x);
fa[rot]=0,cz(rot),deep[rot]=0;
ma[0]=1;
for(int i = head[rot]; i != 0; i = s[i].next) {
if(paint[s[i].to]!=paint[rot]) continue;
++lowbit,yousb[lowbit]=s[i].to,sz[lowbit]=siz[s[i].to];
dfn=0,++color_id,deep[s[i].to]=s[i].val,low(s[i].to);
for(int j = 1; j <= dfn; j++) for(int kk = 1; kk <= kn; kk++)
if(k[kk]-deep[stackk[j]]>=0) ans[kk]+=ma[k[kk]-deep[stackk[j]]];
for(int j = 1; j <= dfn; j++) if(deep[stackk[j]]<=1e7) ma[deep[stackk[j]]]++;
}
for(int i = 1; i <= lowbit; i++) N=sz[i],dfs(yousb[i]);
}
void add_edge(int id,int U,int V,int VAL) {
if(head[U]==0) head[U]=id;
else s[last[U]].next=id;
last[U]=id,s[id].to=V,s[id].val=VAL;
}
int main() {
scanf("%d%d",&n,&kn);
for(int i = 1; i < n; i++) {
scanf("%d%d%d",&u,&v,&q);
add_edge(i*2-1,u,v,q);
add_edge(i*2,v,u,q);
}
for(int i = 1; i <= kn; i++) scanf("%d",&k[i]);
N=n;
dfs(1);
for(int i = 1; i <= kn; i++) printf("%s\n",ans[i]!=0?"AYE":"NAY");
return 0;
}
map
#include<bits/stdc++.h>
using namespace std;
int kn,N,n,k[23333],u,v,q,siz[41111],rot,mas,fa[41111],mi[41111],paint[41111],deep[41111],color_id;
int head[41111],last[41111],ans[23333],stackk[41111],dfn;
struct node{
int to,next,val;
} s[233333];
void find_root(int x){
siz[x]=1,mi[x]=0;
for(int i = head[x]; i != 0; i = s[i].next){
if(s[i].to==fa[x]) continue;
if(paint[s[i].to]!=paint[x]) continue;
fa[s[i].to]=x;
find_root(s[i].to);
mi[x]=max(mi[x],siz[s[i].to]),siz[x]+=siz[s[i].to];
}
mi[x]=max(mi[x],N-siz[x]);
if(mas>mi[x]) mas=mi[x],rot=x;
}
void cz(int x){
siz[x]=1;
for(int i = head[x]; i != 0; i = s[i].next){
if(s[i].to==fa[x]) continue;
if(paint[s[i].to]!=paint[x]) continue;
fa[s[i].to]=x,cz(s[i].to),siz[x]+=siz[s[i].to];
}
}
void low(int x){
for(int i = head[x]; i != 0; i = s[i].next){
if(s[i].to==fa[x]) continue;
if(paint[s[i].to]!=paint[x]) continue;
deep[s[i].to]=deep[x]+s[i].val,fa[s[i].to]=x,low(s[i].to),siz[x]+=siz[s[i].to];
}
++dfn,stackk[dfn]=x,paint[x]=color_id;
}
void dfs(int x){
map<int,int> ma;
if(N==1) return;
int yousb[41111],sz[41111],lowbit=0;
fa[x]=rot=0,mas=1e9,find_root(x);
fa[rot]=0,cz(rot),deep[rot]=0;
ma[0]=1;
for(int i = head[rot]; i != 0; i = s[i].next) {
if(paint[s[i].to]!=paint[rot]) continue;
++lowbit,yousb[lowbit]=s[i].to,sz[lowbit]=siz[s[i].to];
dfn=0,++color_id,deep[s[i].to]=s[i].val,low(s[i].to);
for(int j = 1; j <= dfn; j++) for(int kk = 1; kk <= kn; kk++) ans[kk]+=ma[k[kk]-deep[stackk[j]]];
for(int j = 1; j <= dfn; j++) ma[deep[stackk[j]]]++;
}
for(int i = 1; i <= lowbit; i++) N=sz[i],dfs(yousb[i]);
}
void add_edge(int id,int U,int V,int VAL){
if(head[U]==0) head[U]=id;
else s[last[U]].next=id;
last[U]=id,s[id].to=V,s[id].val=VAL;
}
int main(){
scanf("%d%d",&n,&kn);
for(int i = 1; i < n; i++){
scanf("%d%d%d",&u,&v,&q);
add_edge(i*2-1,u,v,q);
add_edge(i*2,v,u,q);
}
for(int i = 1; i <= kn; i++) scanf("%d",&k[i]);
N=n;
dfs(1);
for(int i = 1; i <= kn; i++) printf("%s\n",ans[i]!=0?"AYE":"NAY");
return 0;
}
by cff_0102 @ 2024-11-13 16:12:47
@麻省理工学院 看人真准
by huhexuan @ 2024-11-13 20:52:04
@麻省理工学院 你说的真的是太对了
by MinimumSpanningTree @ 2024-11-14 13:06:20
@麻省理工学院 预言家/ll
by Vocaloid世末歌者 @ 2024-11-14 13:44:32
@麻省理工学院 拜谢预言家,能不能预测下我今年noip分数和分数线
by Zhi_ptb @ 2024-11-15 18:36:24
@麻省理工学院 考古预言家