点分治板子求调,Sub#3全TLE
查看原帖
点分治板子求调,Sub#3全TLE
739250
Smi1EMAsk楼主2023/6/14 09:33
#include<bits/stdc++.h>
using namespace std;
inline int rd(){
	int num=0,sign=1; char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') sign=-1; ch=getchar();}
	while (ch>='0'&&ch<='9') num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	return num*sign;
}
const int N=1e4+5,M=2e4+5,K=1e7+5,INF=1e9;
int n,m,Q[105];
int h[N],e[M],w[M],ne[M],idx;
void add(int a,int b,int c){
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

bitset<N>vis;
int sz[N],mp[N],cur,ctr;
void get_root(int u,int p){
	sz[u]=1,mp[u]=0;
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		if(v==p||vis[v]) continue;
		get_root(v,u),sz[u]+=sz[v];
		mp[u]=max(mp[u],sz[v]);
	}
	mp[u]=max(mp[u],cur-sz[u]);
	if(mp[u]<mp[ctr]) ctr=u;
}
bitset<K>curex;
int dis[N],path[N],cnt;
void get_dis(int u,int p){
	path[++cnt]=dis[u];
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		if(v==p||vis[v]) continue;
		dis[v]=dis[u]+w[i];
		get_dis(v,u);
	}
}
void calc(int u){
	curex[0]=1;
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		if(vis[v]) continue;
		cnt=0,dis[v]=w[i],get_dis(v,u);
		for(int j=1;j<=cnt;j++)
			for(int k=1;k<=m;k++){
				if(Q[k]>=path[j]&&curex[Q[k]-path[j]])
					Q[k]=-1;
			}
		for(int j=1;j<=cnt;j++) curex[path[j]]=1;
	}
	curex.reset();
}
void solve(int u){
	vis[u]=1;
	calc(u);
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		if(vis[v]) continue;
		cur=sz[v];
		mp[ctr=0]=INF;
		get_root(v,v);
		solve(ctr);
	}
}
int main(){
	n=rd(),m=rd();
	memset(h,-1,sizeof h);
	for(int i=1;i<n;i++){
		int a=rd(),b=rd(),c=rd();
		add(a,b,c),add(b,a,c);
	}
	for(int i=1;i<=m;i++) Q[i]=rd();
	cur=n,mp[ctr=0]=INF,get_root(1,1),solve(ctr);
	for(int i=1;i<=m;i++) 
		puts(Q[i]==-1?"AYE":"NAY");
	return 0;
}
/**
*  ┏┓   ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃       ┃
* ┃   ━   ┃ ++ + + +
*  ████━████+
*  ◥██◤ ◥██◤ +
* ┃   ┻   ┃
* ┃       ┃ + +
* ┗━┓   ┏━┛
*   ┃   ┃ + + + +Code is far away from  
*   ┃   ┃ + bug with the animal protecting
*   ┃    ┗━━━┓ 神兽保佑,代码无bug 
*   ┃        ┣┓
*    ┃        ┏┛
*     ┗┓┓┏━┳┓┏┛ + + + +
*    ┃┫┫ ┃┫┫
*    ┗┻┛ ┗┻┛+ + + +
*/


2023/6/14 09:33
加载中...