点分治求助 有WA 有TLE
查看原帖
点分治求助 有WA 有TLE
275860
___A__楼主2024/6/25 16:04
#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],dis[N],root[N],f[N];
unordered_map<int,int>vis,vis2;
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(unordered_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;
	unordered_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[root[v]]){
	    	ret+=solve(root[v],x);
		}		
	}
	return ret;
}
void dfs1(int u){
    vis2[u]=1,siz[u]=1;
    int num=0,id=0;
    for(auto [v,w]:g[u]){
        if(!vis2[v]){
            f[v]=u,dfs1(v),siz[u]+=siz[v];
            if(siz[v]>num){
                num=siz[v],id=v;
            }
        }
    }
    if(num*2<siz[u]){
        root[u]=u;
        return;
    }
    int tmp=root[id];
    while(siz[u]>siz[tmp]*2){
    	tmp=f[tmp];
	}
	root[u]=tmp;
}
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 16:04
加载中...