淀粉质模板,40TLE,不知道哪超时了qaq
  • 板块P4178 Tree
  • 楼主Jie_Rans
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/10/11 00:26
  • 上次更新2023/10/27 07:55:53
查看原帖
淀粉质模板,40TLE,不知道哪超时了qaq
182792
Jie_Rans楼主2022/10/11 00:26
#include<bits/stdc++.h>
using namespace std;
int read() {
	char ch=getchar();
	int x=0,f=1;
	while(!isdigit(ch)) {
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch)) {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
typedef long long ll;
const int N=1e5+10;
int n,k;
namespace Tree{
	int tot,h[N];
	struct Node{
		int ver,nxt,edge;
	}t[N<<1];
	void addEdge(int x,int y,int z) {
		t[++tot].ver=y; t[tot].nxt=h[x]; t[tot].edge=z; h[x]=tot;
		t[++tot].ver=x; t[tot].nxt=h[y]; t[tot].edge=z; h[y]=tot;
	}
	bool vis[N];
	int size[N],son[N],sum,root;
	void getroot(int x,int fa) {
		size[x]=1; son[x]=0;
		for(int i=h[x];i;i=t[i].nxt) {
			int y=t[i].ver;
			if(y==fa || vis[y]) continue;
			getroot(y,x);
			size[x]+=size[y];
			son[x]=max(son[x],size[y]);
		}
		son[x]=max(son[x],sum-size[x]);
		if(son[root]<son[x]) root=x;
	}
} using namespace Tree;
namespace Solve {
	ll ans;
	int dis[N],que[N],qn,fa[N],d[N],dn;
	ll clac(int x,int len) {
		qn=1; dn=0;
		que[qn]=x; dis[x]=len; fa[x]=0; 
		for(int ql=1;ql<=qn;++ql) {
			int u=que[ql];
			d[++dn]=dis[u];
			for(int i=h[u];i;i=t[i].nxt) {
				int y=t[i].ver,z=t[i].edge;
				if(vis[y] || y==fa[u]) continue;
				fa[y]=u;
				dis[y]=dis[u]+z;
				que[++qn]=y;
			}
		}
		sort(d+1,d+1+dn);
		int l=1,r=dn,cnt=0;
		while(l<r) {
			if(d[l]+d[r]<=k) {
				cnt+=r-l;
				l++;
			}
			else --r;
		}
        return cnt;
	}
	void solve(int u) {
		sum=size[u]; root=0;
		if(!sum) sum=n;
	//	cout<<sum<<endl;
		getroot(u,0);
		vis[root]=true;
//		cout<<"root="<<root<<endl;
		ans+=clac(root,0);
		for(int i=h[root];i;i=t[i].nxt) 
			if(!vis[t[i].ver]) ans-=clac(t[i].ver,t[i].edge);
		for(int i=h[root];i;i=t[i].nxt)
			if(!vis[t[i].ver]) solve(t[i].ver);
	}
} using namespace Solve;
signed main() {
	freopen("exe.in","r",stdin);
    freopen("exe.out","w",stdout);
  	n=read();
  	for(int i=1;i<n;i++) {
  		int x=read(),y=read(),z=read();
  		addEdge(x,y,z);
	}
	k=read();
	sum=n;
	solve(1);
	printf("%lld\n",ans);
}
2022/10/11 00:26
加载中...