求助点分治
查看原帖
求助点分治
356003
Moeebius楼主2022/8/19 21:01

RT, WA on #1,#3,#4,#6,#7qwq\mathtt{WA\ on\ \#1, \#3, \#4, \#6, \#7}\mathrm{ qwq }

#include<bits/stdc++.h>
using namespace std;

#define il inline
#define mkp make_pair
#define pii pair<int,int>
#define lll __int128
#define ll long long
#define For(i,j,k) for(int i=(j); i<=(k); ++i)
#define ForDown(i,j,k) for(int i=(j); i>=(k); --i)
#define pb push_back
#define init(filename) freopen(filename ".in" ,"r",stdin);freopen(filename ".out" ,"w",stdout)
template<typename T> 
il void read(T &x){ x=0;int f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=f;}
template<typename T, typename ... Args>
il void read(T &x, Args &... y){ read(x);read(y...); }

int n,m,root;
vector<pii> T[10001];
struct Query
{
	int k;
	bool ok;
}Q[101];

bool vis[10001];
int sz[10001],maxp[10001],dis[10001],sub[10001],a[10001],tot;

void getRoot(int x, int fa, int sum)
{
	// cerr<<x<<' '<<fa<<' '<<sum<<endl;
	sz[x]=1,maxp[x]=0;
	for(pii ed: T[x])
	{
		int v=ed.first;
		if(v==fa || vis[v]) continue;
		getRoot(v,x,sum);
		sz[x]+=sz[v];
		maxp[x]=max(maxp[x],sz[v]);
	}
	maxp[x]=max(maxp[x],sum-sz[x]);
	if(!root || maxp[x]<maxp[root]) root=x;
}
void getDis(int x, int fa, int w, int rt)
{
	++tot;
	a[tot]=x,dis[tot]=w,sub[tot]=rt;
	for(pii ed: T[x])
	{
		int v=ed.first,dw=ed.second;
		if(v==fa || vis[v]) continue;
		getDis(v,x,w+dw,rt);
	}
}
il bool __cmp_node(const int &a, const int &b){ return dis[a]<dis[b]; }
void cal(int x)
{
	// cerr<<x<<endl;
	tot=1;
	a[tot]=x,dis[tot]=0,sub[tot]=x;
	for(pii ed: T[x])
	{
		int v=ed.first,w=ed.second;
		if(vis[v]) continue;
		getDis(v,x,w,v);
	}
	sort(a+1,a+tot+1,__cmp_node);
	For(i,1,m)
	{
		int l=1,r=tot;
		if(Q[i].ok) continue;
		while(l<r)
		{
			if(dis[a[l]]+dis[a[r]]<Q[i].k) ++l;
			else if(dis[a[l]]+dis[a[r]]>Q[i].k) --r;
			else if(sub[a[l]]==sub[a[r]])
			{
				if(dis[a[r-1]]==dis[a[r]]) --r;
				else ++l;
			}
			else
			{
				Q[i].ok=1;
				break;
			}
		}
	}
}
void solve(int x)
{
	// cout<<x<<endl;
	vis[x]=1;
	cal(x);
	for(pii ed: T[x])
	{
		int v=ed.first;
		if(vis[v]) continue;
		root=0;
		getRoot(v,0,sz[v]);
		solve(root);
	}
}

string ans[]={"AYE","NAY"};

signed main()
{
	read(n,m);
	For(i,1,n-1)
	{
		int u,v,w;
		read(u,v,w);
		T[u].pb(mkp(v,w));T[v].pb(mkp(u,w));
	}
	For(i,1,m)
	{
		read(Q[i].k);
		Q[i].ok=!Q[i].k?1:0;
	}
	root=0;
	maxp[0]=n;
	getRoot(1,0,n);
	solve(root);
	For(i,1,m) printf("%s\n",ans[Q[i].ok^1].c_str());
	return 0;
}
2022/8/19 21:01
加载中...