QNDGXOI
by ZhangJiahao0918 @ 2020-03-15 17:54:18
$$\Large \color{Red} \mathcal{MCWJSMXGXOI}$$
by bellmanford @ 2020-03-15 17:55:46
@[bellmanford](/user/116015)
我表示看不懂
%%%%%
by ZhangJiahao0918 @ 2020-03-15 17:57:40
@[bellmanford](/user/116015) 我记得uoj上有篇博客说有两种找重心的方法都是对的？而且这题数据水
by function_of_zero @ 2020-03-15 17:58:07
刚学OI就蓝勾，太fake了
by mot1ve @ 2020-03-15 17:58:49
@[zzzZF](/user/323144) 这题数据水。。。
by bellmanford @ 2020-03-15 18:00:14
@[bellmanford](/user/116015) 啊，我记得以前是可以用各种方法水过去的，加强一次之后就不知道怎么样了
by function_of_zero @ 2020-03-15 18:01:53
qndmxgxOI 根本看不懂好吧
by dingcx @ 2020-03-15 18:03:05
@[zzzZF](/user/323144) [IEE](https://www.luogu.com.cn/discuss/show/186757)
管理员说了能卡掉所有找错重心的方法，所以这是错误的还是正确的鸭？？？
完整代码：
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
#define max(x,y) (x>y?x:y)
const int M=1e5+5,N=1e7+5;
int n,m,tot=0,cnt=0,sum=0,root=0,maxn=0;
int cc[M],ans[M],dis[M],size[M],query[M],first[M];
bool vis[M],book[N];
struct Edge{
int nxt,to,val;
}e[M<<1];
int read(){
int x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') y=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*y;
}
void add(int x,int y,int z){
e[++tot].nxt=first[x];
first[x]=tot;
e[tot].to=y;
e[tot].val=z;
}
void dfs2(int u,int fa){
cc[++cnt]=u;size[u]=1;
for(int i=first[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].val;
if(v==fa||vis[v]) continue;
dis[v]=dis[u]+w;
dfs2(v,u);
size[u]+=size[v];
}
}
void calc(int u,int w,int c){
cnt=0,dis[u]=w;dfs2(u,0);
for(int i=1;i<=cnt;i++) if(dis[cc[i]]<N) book[dis[cc[i]]]=1;
for(int i=1;i<=cnt;i++)
for(int j=1;j<=m;j++)
if(dis[cc[i]]<=query[j])
if(book[query[j]-dis[cc[i]]])
ans[j]+=c;
for(int i=1;i<=cnt;i++) if(dis[cc[i]]<N) book[dis[cc[i]]]=0;
}
void find_root(int u,int fa){
size[u]=1;
for(int i=first[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa||vis[v]) continue;
find_root(v,u);
size[u]+=size[v];
}
if(maxn>max(size[u],sum-size[u]))
maxn=max(size[u],sum-size[u]),root=u;
}
void dfs(int u){
calc(u,0,1);vis[u]=1;
for(int i=first[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].val;
if(vis[v]) continue;
calc(v,w,-1);sum=size[u],maxn=1e9;
find_root(v,u);dfs(root);
}
}
int main(){
// freopen("P3806_8.in","r",stdin);
// freopen("ans.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n-1;i++){
int x=read(),y=read(),z=read();
add(x,y,z),add(y,x,z);
}
for(int i=1;i<=m;i++) query[i]=read(),ans[i]=0;
sum=n,maxn=1e9;find_root(1,0),dfs(root);
for(int i=1;i<=m;i++) printf("%s\n",ans[i]>0?"AYE":"NAY");
}
```
by bellmanford @ 2020-03-15 18:04:36
但是这个要开O2才能跑过谔谔
by bellmanford @ 2020-03-15 18:05:37