求助点分治 80pts 1点和5点 TLE了(O2不管用)
  • 板块P4178 Tree
  • 楼主Grimgod
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/4/23 16:50
  • 上次更新2023/10/28 03:02:46
查看原帖
求助点分治 80pts 1点和5点 TLE了(O2不管用)
495512
Grimgod楼主2022/4/23 16:50

代码如下:

#include <bits/stdc++.h>
#define int long long
using namespace std;
int vis[40005];
int n,m;
int g,h,ph;
int sizeroot;
int size[40005],weigh[40005];
int cnt[40005],ans[90005],dis[90005];
int k[40006];
int root;
struct Node{
	int to,val;
	Node(int to,int val) :to(to),val(val){}
};
vector <Node > e[40005]; 
inline int read(){
	register int x=0,w=0; char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return w?-x:x; 
}

inline void add(int u,int v,int l){
	e[u].push_back(Node(v,l));
	e[v].push_back(Node(u,l));
}
inline void getcentral(int now,int fa){
	size[now]=1,weigh[now]=0;
	for(register int i=0;i<e[now].size();++i){
		int to=e[now][i].to;
		if(to==fa||vis[to]) continue;
		getcentral(to,now);
		size[now]+=size[to];
		weigh[now]=max(weigh[now],size[to]);
	}
	weigh[now]=max(weigh[now],sizeroot-size[now]);
	if(weigh[root]>weigh[now]) root=now;
}
inline void clean_cnt(int now,int fa,int len){
	if(len<=10000000) cnt[len]=0;
	for(register int i=0;i<e[now].size();++i){
		int to=e[now][i].to;
		if(to==fa||vis[to]) continue;
		clean_cnt(to,now,len+e[now][i].val);
	}  
}
inline void change_cnt(int now,int fa,int len){
	if(len<=10000000) cnt[len]++;
	for(register int i=0;i<e[now].size();++i){
		int to=e[now][i].to;
		if(to==fa||vis[to]) continue;
		change_cnt(to,now,len+e[now][i].val);
	} 
}
inline void change_ans(int now,int fa,int len){
	for(register int i=1;i<=m;++i){
		if(len<=k[i]){
			ans[i]+=cnt[k[i]-len];
		}
	}
	for(register int i=0;i<e[now].size();++i){
		int to=e[now][i].to;
		if(to==fa||vis[to]) continue;
		change_ans(to,now,len+e[now][i].val);
	} 
}
inline void divide(int now){
	vis[now]=1;
	cnt[0]=1;
	for(register int i=0;i<e[now].size();++i){
		int to=e[now][i].to;
		if(vis[to]) continue;
		change_ans(to,now,e[now][i].val);
		change_cnt(to,now,e[now][i].val);	
	} 
	clean_cnt(now,0,0);
	for(register int i=0;i<e[now].size();++i){
		int to=e[now][i].to;
		if(vis[to]) continue;
		root=0,weigh[0]=0x3f3f3f;
		sizeroot=size[to];
		getcentral(to,now);
		divide(root); 
	}
}
int tot;
signed main(){
	n=read();
	for(register int i=1;i<=n-1;++i){
		g=read(),h=read(),ph=read();
		add(g,h,ph);
	}
	g=read();
	m=g+1;
	for(register int i=0;i<=g;++i){
		k[++tot]=i;
	}
	int cnt=0;
	sizeroot=n,root=0,weigh[root]=0x3f3f3f;
	getcentral(1,0);
	divide(root);
	for(register int i=1;i<=m;++i){
		cnt+=ans[i];
	}
	cout<<cnt;
	return 0;
} 

2022/4/23 16:50
加载中...