点分治全TLE求助 重心有误
查看原帖
点分治全TLE求助 重心有误
275860
___A__楼主2024/6/25 14:05
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
struct graph{
	int v,w;
};
vector<graph>g[N];
int n,T,siz[N],id,val,dis[N],all[N];
map<int,int>vis,vis2;
void dfs(int u,int anc){
    vis2[u]=1,siz[u]=1;
    int now=0;
    for(auto [v,w]:g[u]){
        if(!vis2[v]){
            dfs(v,u),siz[u]+=siz[v],now=max(now,siz[v]);
        }
    }
    now=max(now,all[anc]-siz[u]);
    if(now<val){
        val=now,id=u;
    }
}
int root(int u){
    vis2.clear(),val=1e9,dfs(u,u);
	return id;
}
void dfs(int u){
    vis2[u]=1;
    for(auto [v,w]:g[u]){
        if(!vis2[v]){
            dis[v]=dis[u]+w,dfs(v);
        }
    }
}
void ins(multiset<int>&x,int u){
    vis2[u]=1,x.insert(dis[u]);
    for(auto [v,w]:g[u]){
        if(!vis2[v]){
            ins(x,v);
        }
    }
}
int calc(int u,int x){
	vis2.clear(),dis[u]=0,dfs(u);
	int cnt=0;
	multiset<int>S[N],pre[N];
	pre[0].insert(0);
	for(auto [v,w]:g[u]){
	    if(!vis[v]){
	        cnt++,vis2.clear(),ins(S[cnt],v),pre[cnt]=pre[cnt-1];
	        auto tmp=S[cnt];
	        while(tmp.size()){
	            pre[cnt].insert(*(tmp.begin())),tmp.erase(tmp.find(*tmp.begin()));
	        }
	    }
	}
	for(int i=1;i<=cnt;i++){
	    for(int j:S[i]){
	        if(pre[i-1].count(x-j)){
	            return 1;
	        }
	    }
	}
	return 0;
}
int solve(int u,int x){
	vis[u]=1;
	int ret=calc(u,x);
	for(auto [v,w]:g[u]){
	    if(!vis[v]){
	    	ret+=solve(root(v),x);
		}		
	}
	return ret;
}
void dfs1(int u){
    vis2[u]=1,all[u]=1;
    for(auto [v,w]:g[u]){
        if(!vis2[v]){
            dfs1(v),all[u]+=all[v];
        }
    }
}
int main(){
	cin>>n>>T;
	for(int i=1,u,v,w;i<n;i++){
		cin>>u>>v>>w,g[u].push_back({v,w}),g[v].push_back({u,w});
	}
	vis2.clear(),dfs1(1);
	for(int x;T--;){
		vis.clear(),cin>>x;
		if(solve(root(1),x)){
			cout<<"AYE\n";
		}
		else{
			cout<<"NAY\n";
		}
	}
}
2024/6/25 14:05
加载中...