MnZn求助,点分治板题全T
  • 板块灌水区
  • 楼主忘怜城羡
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/2/28 22:01
  • 上次更新2024/2/29 13:47:09
查看原帖
MnZn求助,点分治板题全T
374756
忘怜城羡楼主2024/2/28 22:01
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+7;
vector<pair<int,int> > g[MAXN];
struct node{
	int d,f;
	bool operator < (const node &x){
		return d<x.d;
	}
	void add(int x,int y)
	{
		d=x,f=y;
		return ;
	}
}a[MAXN];
int q[MAXN],size[MAXN],weight[MAXN],n,m,root,tot;
bool vis[MAXN],op[MAXN];
void dfs(int x,int from,int s)
{
	size[x]=1;
	weight[x]=0;
	for(int i(0);i<g[x].size();++i)
		if(g[x][i].first!=from)
		{
			dfs(g[x][i].first,x,s);
			size[x]+=size[g[x][i].first];
			weight[x]=max(weight[x],size[g[x][i].first]);
		}
	weight[x]=max(weight[x],s-size[x]);
	if(!root||weight[x]<weight[root])
		root=x;
	return ;
}
void dis(int x,int from,int len,int t)
{
	a[++tot].add(len,t);
	for(int i(0);i<g[x].size();++i)
		if(!op[g[x][i].first]&&g[x][i].first!=from)
			dis(g[x][i].first,x,len+g[x][i].second,t);
}
void calc(int x)
{
	tot=0;
	a[++tot].add(0,x);
	for(int i(0);i<g[x].size();++i)
		if(!op[g[x][i].first])
			dis(g[x][i].first,x,g[x][i].second,g[x][i].first);
	sort(a+1,a+tot+1);
	int l,r;
	for(int i(1);i<=m;++i)
		if(!vis[i])
		{
			l=1,r=tot;
			while(l<r)
				if(a[l].d+a[r].d>q[i])
					r--;
				else
					if(a[l].d+a[r].d<q[i])
						l++;
					else
						if(a[l].f==a[r].f)
						{
							if(a[r].d==a[r-1].d)
								r--;
							else
								l++;
						}
						else
						{
							vis[i]=1;
							break;
						}
		}
	return ;
}
void work(int x)
{
	op[x]=1;
	calc(x);
	for(int i(0);i<g[x].size();++i)
		if(!vis[g[x][i].first])
		{
			root=0;
			dfs(g[x][i].first,x,size[g[x][i].first]);
			work(root); 
		}
}
int main()
{
	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(make_pair(v,w));
		g[v].push_back(make_pair(u,w));
	}
	for(int i(1);i<=m;++i)
	{
		scanf("%d",&q[i]);
		if(!q[i])
			vis[i]=1;
	}
	dfs(1,0,n);
	work(root);
	for(int i(1);i<=m;++i)
		if(vis[i])
			printf("AYE\n");
		else
			printf("NAY\n");
	return 0;
}
2024/2/28 22:01
加载中...