chlchl @ 2022-01-21 08:22:31
昨天发暴力代码 RE 的帖解决了,今天又 RE 了……
真和 RE 过不去了 ORZ。
今天更奇怪,本地运行第一组数据是 AC 的,洛谷 RE。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
const int M = 1e7 + 10;
int n, m, rt, SZ, q[N], ans[M];
int sz[N], mson[N];
int len, dis[N], emp[M], dis_son[M], is_ok[M];
bool visit[N];
struct edge{int u, v, w;};
vector<edge> g[N];
void dfs(int u, int fa){
sz[u] = 1, mson[u] = 0;
for(int i=0;i<g[u].size();i++){
int v = g[u][i].v;
if(v != fa && !visit[v]){
dfs(v, u);
mson[u] = max(mson[u], sz[v]);
sz[u] += sz[v];
}
}
mson[u] = max(mson[u], SZ - sz[u]);
if(mson[u] < mson[rt]) rt = u;
}
int query(int u, int fa){
dis_son[++len] = dis[u];
for(int i=0;i<g[u].size();i++){
int v = g[u][i].v, w = g[u][i].w;
if(visit[v] || v == fa) continue;
dis[v] = dis[u] + w;
query(v, u);
}
}
void solve(int u){
int pos = 0;
for(int i=0;i<g[u].size();i++){
int v = g[u][i].v, w = g[u][i].w;
if(visit[v]) continue;
len = 0, dis[v] = w;
query(v, u);
for(int j=len;j;j--){//遍历子树距离
for(int l=1;l<=m;l++){
if(q[l] >= dis_son[j]) ans[l] |= is_ok[q[l] - dis_son[j]];
}
}
for(int j=len;j;j--) emp[++pos] = dis_son[j], is_ok[dis_son[j]] = 1;
}
for(int i=1;i<=pos;i++) is_ok[emp[i]] = 0;
}
void divide(int u){
visit[u] = is_ok[0] = 1;
solve(u);
for(int i=0;i<g[u].size();i++){
int v = g[u][i].v, w = g[u][i].w;
if(visit[v]) continue;
solve(v);
SZ = sz[u], rt = 0, mson[rt] = 1e9;
dfs(v, 0);
// cout << rt << endl;
divide(rt);
}
}
int main(){
// freopen("1.txt", "w", stdout);
scanf("%d%d", &n, &m);
for(int i=1;i<n;i++){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].push_back((edge){u, v, w});
g[v].push_back((edge){v, u, w});
}
for(int i=1;i<=m;i++) scanf("%d", &q[i]);
SZ = n, mson[rt] = 1e9;
dfs(1, 0);
divide(rt);
for(int i=1;i<=m;i++){
if(ans[i]) puts("AYE");
else puts("NAY");
}
return 0;
}
by chlchl @ 2022-01-21 08:53:55
@_k_e_v_in 那应该是 void,我写错了
by chlchl @ 2022-01-21 08:54:30
@小鸭子天山 那算了.不过既然来都来了,帮我这个蒟蒻调个题?
by chlchl @ 2022-01-21 08:55:50
@_k_e_v_in 过了,真的就是加了个 return!谢谢大佬 %%%
by DPseud @ 2022-01-21 08:55:57
刚学OI第二天?
by chlchl @ 2022-01-21 08:56:08
本帖完结
by _k_e_v_i_n_ @ 2022-01-21 08:57:01
@caihaolang az
by 小鸭子天山 @ 2022-01-21 08:57:24
@caihaolang 我¥%#!%#¥……¥#%&#@¥%……#@%¥%@%¥……%&@……%¥#
by chlchl @ 2022-01-21 08:58:40
@小鸭子天山 没事调完了,AC 了……
by chlchl @ 2022-01-21 08:59:16
@_k_e_v_in 不过话说为啥加了个 return 就过了呢?这个位置本来就应该是结束了的呀……
by _k_e_v_i_n_ @ 2022-01-21 09:01:13
@caihaolang int类型函数(有返回值)不return就会RE,void类型函数(没有返回值)就不会。