TLE on #7
查看原帖
TLE on #7
373938
wowwowwow楼主2024/8/18 15:48
#include<bits/stdc++.h>
using namespace std;

const int N = 1e4 + 7;
bool flag = false;
int n, m, k, cnt, dl[N], delt[N], sz[N], mx[N], RT[N], lzx, lx, id = 0;
bool val[10000007], vis[N];
vector< pair<int,int> > g[N];

void getdis(int u, int fa, int sum){
	dl[++cnt] = sum;
	for(auto pi : g[u]){
		int v = pi.first, w = pi.second;
		if(v != fa && !vis[v]){
			getdis(v, u, sum + w);
		}
	}
	return;
}

void dfs(int u, int fa){
	sz[u] = 1; mx[u] = 0; dl[++cnt] = u;
	for(auto pi : g[u]){
		int v = pi.first, w = pi.second;
		if(v != fa && !vis[v]){
			dfs(v, u);
			mx[u] = max(mx[u], sz[v]);
			sz[u] += sz[v];
		}
	}
	return;
}

void solve(int x){
	int rt = RT[++id], tot = 0;
	vis[rt] = 1;
//	cout << x << ' ' << rt << '\n';
	for(pair<int, int> pi : g[rt]){
		int v = pi.first, w = pi.second;
		cnt = 0;
		if(vis[v]) continue;
		getdis(v, rt, w);
//		cout << "xxx:";
//		for(int i = 1; i <= cnt; i++)
//			cout << dl[i] << ' ';
//		cout << '\n';
		for(int i = 1; i <= cnt; i++)
			if(dl[i] == k || dl[i] < k && val[k - dl[i]]){
				flag = true; 
			}
		for(int i = 1; i <= cnt; i++){
			if(dl[i] <= 1e7 && !val[dl[i]]){
				delt[++tot] = dl[i];
				val[dl[i]] = 1;	
			}
		}
		cnt = 0;
	}
	for(int i = 1; i <= tot; i++)
		val[delt[i]] = 0;
 	for(pair<int, int> pi : g[rt]){
		int v = pi.first, w = pi.second;
		if(!vis[v]) solve(v);
	}
	return;
}

void getrt(int u){
	cnt = 0;  
	dfs(u, 0);
	int rt = u, mi = 1e9;
	for(int i = 1; i <= cnt; i++){
		mx[dl[i]] = max(mx[dl[i]], sz[u] - sz[dl[i]]);
		if(mx[dl[i]] < mi){
			mi = mx[dl[i]];
			rt = dl[i];
		}
	}
	RT[++id] = rt;
	vis[rt] = 1;
	for(auto pi : g[rt]){
		int v = pi.first, w = pi.second;
		if(!vis[v]) getrt(v);
	}
	return;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); 
	cin >> n >> m;
	for(int i = 1; i < n; i++){
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back(make_pair(v, w)); g[v].push_back(make_pair(u, w));
	}
	getrt(1);
	while(m--){
		cin >> k;	
		for(int i = 1; i <= n; i++)
			vis[i] = 0;
		flag = false; id = 0;
		solve(1);
		if(flag) cout << "AYE" << '\n';
		else cout << "NAY" << '\n';
	}
	return 0;
}

我是先建点分树再统一询问

2024/8/18 15:48
加载中...