今天我刷题了吗
搜索文档…
点分治
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const int maxn(1e4 + 10);
7
const int maxm(1e2 + 10);
8
const int maxk(2e7 + 10);
9
int ecnt, head[maxn];
10
int que[maxm], ans[maxn];
11
int rt, tot, root[maxn], siz[maxn], maxp[maxn];
12
int cnt, tmp[maxn], dis[maxn];
13
bool vis[maxn], judge[maxk];
14
15
struct edge {
16
int to, wt, nxt;
17
} edges[maxn << 1];
18
19
template<typename T = int>
20
inline const T read()
21
{
22
T x = 0, f = 1;
23
char ch = getchar();
24
while (ch < '0' or ch > '9') {
25
if (ch == '-') f = -1;
26
ch = getchar();
27
}
28
while (ch >= '0' and ch <= '9') {
29
x = (x << 3) + (x << 1) + ch - '0';
30
ch = getchar();
31
}
32
return x * f;
33
}
34
35
template<typename T>
36
inline void write(T x, bool ln)
37
{
38
if (x < 0) {
39
putchar('-');
40
x = -x;
41
}
42
if (x > 9) write(x / 10, false);
43
putchar(x % 10 + '0');
44
if (ln) putchar(10);
45
}
46
47
inline void addEdge(int u, int v, int w)
48
{
49
edges[ecnt].to = v;
50
edges[ecnt].wt = w;
51
edges[ecnt].nxt = head[u];
52
head[u] = ecnt++;
53
}
54
55
void getRoot(int u, int f)
56
{
57
siz[u] = 1;
58
maxp[u] = 0;
59
for (int i = head[u]; compl i; i = edges[i].nxt) {
60
int v = edges[i].to;
61
if (vis[v] or v == f) {
62
continue;
63
}
64
getRoot(v, u);
65
siz[u] += siz[v];
66
maxp[u] = max(maxp[u], siz[v]);
67
}
68
maxp[u] = max(maxp[u], tot - siz[u]);
69
if (maxp[u] < maxp[rt]) {
70
rt = u;
71
}
72
}
73
74
void getDis(int u, int f)
75
{
76
tmp[cnt++] = dis[u];
77
for (int i = head[u]; compl i; i = edges[i].nxt) {
78
int v = edges[i].to, w = edges[i].wt;
79
if (vis[v] or v == f) {
80
continue;
81
}
82
dis[v] = dis[u] + w;
83
getDis(v, u);
84
}
85
}
86
87
void solve(int u, int m)
88
{
89
static queue<int> q;
90
for (int i = head[u]; compl i; i = edges[i].nxt) {
91
int v = edges[i].to, w = edges[i].wt;
92
if (vis[v]) {
93
continue;
94
}
95
cnt = 0;
96
dis[v] = w;
97
getDis(v, u);
98
for (int j = 0; j < cnt; ++j) {
99
for (int k = 0; k < m; ++k) {
100
if (que[k] >= tmp[j]) {
101
ans[k] or_eq judge[que[k] - tmp[j]];
102
}
103
}
104
}
105
for (int j = 0; j < cnt; ++j) {
106
q.push(tmp[j]);
107
judge[tmp[j]] = true;
108
}
109
}
110
while (not q.empty()) {
111
judge[q.front()] = false;
112
q.pop();
113
}
114
}
115
116
void divide(int u, int m)
117
{
118
vis[u] = judge[0] = true;
119
solve(u, m);
120
for (int i = head[u]; compl i; i = edges[i].nxt) {
121
int v = edges[i].to;
122
if (vis[v]) {
123
continue;
124
}
125
maxp[rt = 0] = tot = siz[v];
126
getRoot(v, 0);
127
getRoot(rt, 0);
128
divide(rt, m);
129
}
130
}
131
132
int main()
133
{
134
#ifndef ONLINE_JUDGE
135
freopen("input.txt", "r", stdin);
136
#endif
137
memset(head, -1, sizeof head);
138
int n = read(), m = read();
139
for (int i = 0; i < n - 1; ++i) {
140
int u = read(), v = read(), w = read();
141
addEdge(u, v, w);
142
addEdge(v, u, w);
143
}
144
for (int i = 0; i < m; ++i) {
145
que[i] = read();
146
}
147
tot = maxp[0] = n;
148
getRoot(1, 0);
149
getRoot(rt, 0);
150
divide(rt, m);
151
for (int i = 0; i < m; ++i) {
152
puts(ans[i] ? "AYE" : "NAY");
153
}
154
return 0;
155
}
Copied!
最近更新 11mo ago
复制链接