MnZn刚学点分治1ms,20分tle代码求调/kel
查看原帖
MnZn刚学点分治1ms,20分tle代码求调/kel
386795
一只小咕咕楼主2024/1/4 17:42

#2,#4 A 了,#3是WA,其余的全 TLE

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
inline int read();
int n,head[N],cnt,size[N],maxp[N],tot,a[N],dis[N],pos[N],root,k;
long long ans;
bool vis[N];
struct E{
	int to,next,w;
}edge[N<<1];
void add(int u,int v,int w)
{
	edge[++cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
void get_root(int x,int fa,int sum)
{
	size[x]=1;
	maxp[x]=0;
	for(int i=head[x];i;i=edge[i].next)
	{
		int to=edge[i].to;
		if(to==fa||vis[to]) continue;
		get_root(to,x,sum);
		size[to]+=size[x];
		maxp[x]=max(maxp[x],size[to]);
	}
	maxp[x]=max(maxp[x],sum-maxp[x]);
	if(!root||maxp[x]<maxp[root]) root=x;
}
bool cmp(int x,int y)
{
	return dis[x]<dis[y];
}
void get_dis(int x,int fa,int val,int from)
{
	a[++tot]=x;
	dis[x]=val;
	pos[x]=from;
	for(int i=head[x];i;i=edge[i].next)
	{
		int to=edge[i].to;
		if(to==fa||vis[to]) continue;
		get_dis(to,x,val+edge[i].w,from);
	}
}
long long calc(int x,int w)
{
	long long sum=0;
	tot=0;
	a[++tot]=x;
	dis[x]=0;
	pos[x]=x;
	for(int i=head[x];i;i=edge[i].next)
	{
		int to=edge[i].to;
		if(vis[to]) continue;
		get_dis(to,x,edge[i].w+w,to);
	}
	sort(a+1,a+1+tot,cmp);
	int l=1,r=tot;
	while(l<r)
	{
		if(dis[a[l]]+dis[a[r]]>k)
		{
			r--;
		}
		else if(dis[a[l]]+dis[a[r]]<=k)
		{
			sum+=r-l;
			l++;
		}
	}
	return sum;
}
void solve(int x)
{
	vis[x]=1;
	ans+=calc(x,0);
	for(int i=head[x];i;i=edge[i].next)
	{
		int to=edge[i].to;
		if(vis[to]) continue;
		ans-=calc(to,edge[i].w);
		root=0;
		get_root(to,0,size[to]);
		solve(root);
	}
}
int main()
{
	n=read();
	for(int i=1;i<n;i++)
	{
		int x,y,z;
		x=read();y=read();z=read();
		add(x,y,z);
		add(y,x,z);
	}
	k=read();
	maxp[0]=n;
	get_root(1,0,n);
	solve(root);
	printf("%lld",ans);
	return 0;
}

inline int read()
{
	int x=0,f=1;
	char ch;
	ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-') f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')
	{
		x=(x<<1)+(x<<3)+(ch&15);
		ch=getchar();
	}
    return x*f;
}


2024/1/4 17:42
加载中...