求调点分治,调了一天调崩溃了QAQ
查看原帖
求调点分治,调了一天调崩溃了QAQ
1420058
HaloisAWA楼主2024/11/10 23:41
#include<bits/stdc++.h>
using namespace std;
struct node{
	int v,w;
	node(int vv,int ww) {
		v = vv;
		w = ww;
		return;
	}
};
int n,m,ut,vt,wt,k;
long long dp[40010],dis[40010],maxn,ans;
vector<node> g[40010];
vector<pair<long long,int> > d;
bool vis[40010];
int center,l,r,cnt;
void dfs1(int u,int fa) {
	long long tmp = 0;
	dp[u] = 1;
	for (int i = 0;i < g[u].size();i ++) {
		int v = g[u][i].v,w = g[u][i].w;
		if (v != fa && (!vis[v])) {
			dfs1(v,u);
			dp[u] += dp[v];
			tmp = max(tmp,dp[v]);
		}
	}
	tmp = max(tmp,cnt - dp[u]);//////
	if (tmp < maxn) center = u;
	return;
}
void dfs2(int u,int fa,int colr) {
	d.push_back(make_pair(dis[u],colr));//放在这里是为了保证根节点进入vector 
	for (int i = 0;i < g[u].size();i ++) {
		int v = g[u][i].v,w = g[u][i].w;
		if (v != fa && (!vis[v])) {
			dis[v] = dis[u] + w;//这句话放在dfs2前面 
			dfs2(v,u,colr);
		}
	}
	return;
}
void calc(int u,int val) {
	dis[u] = 0;//
	d.clear();//
	
	d.push_back(make_pair(dis[u],u));
	for (int i = 0;i < g[u].size();i ++) {
		int v = g[u][i].v,w = g[u][i].w;
		if (!vis[v]) {
			dis[v] = dis[u] + w;
			dfs2(v,u,v);
		}
	}
	
	sort(d.begin(),d.end());//
	l = 0;
	r = d.size() - 1;
	while (l < r) {
		if (d[l].first + d[r].first == val) {
			printf("AYE\n");
			exit(0);
		} else if (d[l].first + d[r].first < val) ++ l;
		else -- r;
	}
	return;
}
void solve(int u) {
	vis[u] = true;
	calc(u,k);
	for (int i = 0;i < g[u].size();i ++) {
		int v = g[u][i].v,w = g[u][i].w;
		if (!vis[v]) {
			cnt = dp[v];//
			maxn = 0x7fffffff;//
			dfs1(v,0);
			solve(center);
		}
	}
	return;
}
int main() {
	scanf("%d%d",&n,&m);
	for (int i = 1;i < n;i ++) {
		scanf("%d%d%d",&ut,&vt,&wt);
		g[ut].push_back(node(vt,wt));
		g[vt].push_back(node(ut,wt));
	}
	for (int kkk = 1;kkk <= m;kkk ++) {
		scanf("%d",&k);
		maxn = 0x7fffffff;
		cnt = n;
		dfs1(1,0);//找重心 
		//dis[center] = 0;
		solve(center);
		printf("NAY\n");
	}
	return 0;
}

2024/11/10 23:41
加载中...