Timing @ 2019-07-16 13:40:45
样例可以过,评测爆零全MLE,应该是递归爆栈,但真的不知道那炸掉了,
```cpp
using namespace std;
int main() {}
#include<bits/stdc++.h>
#define rt register int
#define gt getchar()
#define INF 10000000
const int _ = 1e5 + 10;
namespace OI {
struct _Main {
int n,m,root,Size,f[_],siz[_],dis[_],sum[_],plus[1010];
int exist[_],judge[_],down[_];
int cnt,head[_],ver[_<<1],nxt[_<<1],edge[_<<1];
bool used[_];
inline void add (int u, int v, int w) {
ver[++cnt] = v;
nxt[cnt] = head[u];
edge[cnt] = w;
head[u] = cnt;
}
inline void Get_Root (int u, int fa) {
f[u] = 0, siz[u] = 1; rt i;
for (i = head[u]; i; i = nxt[i]){
int v = ver[i];
if(used[v] or v == fa) continue;
Get_Root(v,u);
f[u] = max(f[u],siz[v]);
siz[u] += siz[v];
}
f[u] = max(f[u],Size - siz[u]);
if(f[u] < f[root]) root = u;
}
inline void Get_Dis (int u, int fa) {
sum[++sum[0]] = dis[u]; rt i;
for (i = head[u]; i; i = nxt[i]){
int v = ver[i];
if(used[v] or v == fa) continue;
dis[v] = dis[u] + edge[i];
Get_Dis(v,u);
}
}
inline void Calc (int u) {
rt p = 0, i, j, k;
for (i = head[u]; i; i = nxt[i]){
int v = ver[i];
if(used[v]) continue;
sum[0] = 0; dis[v] = edge[i];
Get_Dis(v,u);
for (j = sum[0]; j; --j)
for (k = 1; k <= m; ++k)
if(plus[k] >= sum[j])
exist[k] |= judge[plus[k] - sum[j]];
for (j = sum[0]; j; --j)
down[++p] = sum[j], judge[sum[j]] = 1;
}
for (i = 1; i <= p; ++i)
judge[down[i]] = 0;
}
inline void solve (int u) {
used[u] = (judge[0] = 1);
Calc(u); rt i;
for (i = head[u]; i; i = nxt[i]){
int v = ver[i];
if(used[i]) continue;
Size = siz[v]; f[root = 0] = INF;
Get_Root(v,0); solve(root);
}
}
_Main() {
read(n); read(m); rt i, u, v, w;
for (i = 1; i < n; ++i){
read(u); read(v); read(w);
add(u,v,w); add(v,u,w);
}
for (i = 1; i <= m; ++i) read(plus[i]);
f[root] = Size = n;
Get_Root(1,0); solve(root);
for (i = 1; i <= m; ++i){
if(exist[i]) puts("AYE");
else puts("NAY");
}
}
template <typename Type>
inline void read(Type &x) {
char s, f = 1;
while(!isdigit(s = gt)) f = (s == '-') ? -1 : 1;
x = s ^ 48;
while(isdigit(s = gt)) x = (x<<1) + (x<<3) + (s ^ 48);
x *= f;
}
} std;
}
```
感谢进来的巨佬们,~~明年你们都AK NOI~~