Erine @ 2022-12-03 19:42:22
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
struct ios {
inline char read() {
static const int inlen = 1 << 18 | 1;
static char buf[inlen], *s, *t;
return (s == t) && (t = (s = buf) + fread(buf, 1, inlen, stdin)), s == t ? -1 : *s++;
}
template<typename T> inline ios& operator>> (T &x) {
static char c11, boo;
for (c11 = read(), boo = 0; !isdigit(c11); c11 = read()) {
if (c11 == -1) return *this;
boo |= c11 == '-';
}
for (x = 0; isdigit(c11); c11 = read()) x = x * 10 + (c11 ^ '0');
boo && (x = -x);
return *this;
}
} fin;
struct exios {
template<typename _CharT, typename _Traits = char_traits<_CharT>>
struct typ {
typedef basic_ostream<_CharT, _Traits>& (* end) (basic_ostream<_CharT, _Traits>&);
};
friend exios &operator<<(exios &out, int num) {
if (num < 0) putchar('-'), num = -num;
if (num >= 10) out << num / 10;
putchar(num % 10 + '0');
return out;
}
friend exios &operator<<(exios &out, const char * s) { printf("%s", s); return out; }
friend exios &operator<<(exios &out, string s) { cout << s; return out; }
friend exios &operator<<(exios &out, typ<char>::end e) { puts(""); return out; }
} fout;
const int maxn = 1e4 + 1;
const int maxm = 1e4 + 1;
const int maxq = 1e3 + 1;
const int maxv = 1e7 + 1;
struct edge {
int to, next, w;
};
int n, m, k[maxq];
int head[maxn];
edge e[maxm << 1];
int cnt;
void add_edge(int u, int v, int w) {
e[++cnt].to = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt;
}
int tot, root, ans[maxq];
int mx[maxn];
int siz[maxn];
int vis[maxn];
void get_root(int u, int fa) {
mx[u] = 0;
siz[u] = 1;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (v == fa || vis[v]) continue;
get_root(v, u);
siz[u] += siz[v];
mx[u] = max(mx[u], siz[v]);
}
mx[u] = max(mx[u], tot - siz[u]);
if (mx[u] < mx[root]) {
root = u;
}
}
int dep[maxn], num;
void get_dep(int u, int d, int fa) {
dep[++num] = d;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to, w = e[i].w;
if (v == fa || vis[v]) continue;
get_dep(v, d + w, u);
}
}
int book[maxv];
int get_sum(int u, int dis, int id) {
num = 0;
get_dep(u, dis, 0);
int sum = 0;
for (int i = 1; i <= num; ++i) {
if (k[id] >= dep[i]) sum += book[k[id] - dep[i]];
if (dep[i] < maxv) ++book[dep[i]];
}
for (int i = 1; i <= num; ++i) {
if (dep[i] < maxv) book[dep[i]] = 0;
}
return sum;
}
void solve(int u) {
for (int i = 1; i <= m; i++) {
ans[i] += get_sum(u, 0, i);
}
vis[u] = true;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to, w = e[i].w;
if (vis[v]) continue;
for (int j = 1; j <= m; j++) {
ans[j] -= get_sum(v, w, j);
}
tot = siz[v];
root = 0;
get_root(v, u);
solve(root);
}
}
signed main() {
// freopen("P3806_1.in", "r", stdin);
// freopen("P3806_1.out", "w", stdout);
fin >> n >> m;
for (int i = 1; i <= n - 1; i++) {
int u, v, w;
fin >> u >> v >> w;
add_edge(u, v, w);
add_edge(v, u, w);
}
mx[0] = 1e9;
for (int i = 1; i <= m; i++) {
fin >> k[i];
}
tot = n;
get_root(1, 0);
solve(root);
for (int i = 1; i <= m; i++) {
cout << (ans[i] ? "AYE" : "NAY") << endl;
}
return 0;
}
by a2lyaXNhbWUgbWFyaXNh @ 2022-12-03 19:55:28
@Eachbranch 试试红黑树快读?
by a2lyaXNhbWUgbWFyaXNh @ 2022-12-03 19:56:16
而且你最后是cout
by a2lyaXNhbWUgbWFyaXNh @ 2022-12-03 19:56:52
C++98 开register 还有inline
by a2lyaXNhbWUgbWFyaXNh @ 2022-12-03 19:59:16
提示
本题不卡常
by a2lyaXNhbWUgbWFyaXNh @ 2022-12-03 19:59:49
https://www.luogu.com.cn/discuss/188596
by WaReTle @ 2022-12-03 20:01:50
复杂度假了
人家正经点分治都跑几十ms
应该是solve里面递归下去的时候tot错了