TLE #7#9,帮我AC变猫娘
查看原帖
TLE #7#9,帮我AC变猫娘
620253
MvemiY楼主2025/7/16 16:10
#include<bits/stdc++.h>
#define T(v, w) (TNode){v, w}
using namespace std;
const int MAXN = 1e4 + 10, inf = 1e7 + 10;

inline int read(){
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}

int n, m, qs[MAXN];
int rot, siz[MAXN], sum, mx, cnt, dis[MAXN];
int pre[MAXN];
bool del[MAXN], ans[MAXN], bok[inf];
struct TNode{
	int v, w;
};
vector <TNode> tr[MAXN];

void dfs1(int u, int pp){ // 寻找新的 rot 
	int len = tr[u].size();
	siz[u] = 1;
	int res = 0;
	for(int i = 0; i < len; i++){
		int v = tr[u][i].v;
		if(v == pp || del[v]) continue;
		dfs1(v, u);
		siz[u] += siz[v];
		if(res > siz[v]){
			res = siz[v];
			rot = u;
		}
//		res = max(res, siz[v]);
	}
	res = max(res, sum - siz[u]);
	if(res < mx) rot = u, mx = res;
}

void dfs2(int u, int pp){ // 处理 pre 
	int len = tr[u].size();
	dis[++cnt] = pre[u];
	for(int i = 0; i < len; i++){
		int v = tr[u][i].v, w = tr[u][i].w;
		if(del[v] || v == pp) continue;
		pre[v] = pre[u] + w;
		dfs2(v, u);
	}
}

int q[MAXN];

void calc(int u){
	bok[0] = true;
	int tot = 0;
	int len = tr[u].size();
	for(int i = 0; i < len; i++){
		int v = tr[u][i].v, w = tr[u][i].w;
		if(del[v]) continue;
		cnt = 0;
		pre[v] = w;
		dfs2(v, u);
		for(int j = 1; j <= cnt; j++)
			for(int k = 1; k <= m; k++)
				if(qs[k] >= dis[j])
					ans[k] |= bok[qs[k] - dis[j]] ;
		for(int j = 1; j <= cnt; j++)
			if(dis[j] < inf)
				q[++tot] = dis[j], bok[dis[j]] = true;
	}
	for(int i = 1; i <= tot; i++)
		bok[q[i]] = false;
}

void solve(int u){
	del[u] = true;
	calc(u);
	int len = tr[u].size();
	for(int i = 0; i < len; i++){
		int v = tr[u][i].v;
		if(del[v]) continue;
		mx = 0x3f3f3f3f;
		sum = siz[v];
		dfs1(v, u);
		solve(rot);
	}
}

int main(){
	n = read(), m = read();
	for(int i = 1; i < n; i++){
		int u = read(), v = read(), w = read();
		tr[u].push_back(T(v, w));
		tr[v].push_back(T(u, w));
	}
	for(int i = 1; i <= m; i++)
		qs[i] = read();
	sum = n;
	mx = 0x3f3f3f3f;
	dfs1(1, 0);
	solve(rot);
	for(int i = 1; i <= m; i++){
		if(ans[i]) puts("AYE");
		else puts("NAY");
	}
	return 0;
} 

rt,估计是重心找的不对,但是瞪不出来QWQ

2025/7/16 16:10
加载中...