code厌氧
  • 板块P4178 Tree
  • 楼主langligelang
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/5/4 17:19
  • 上次更新2023/10/23 16:41:23
查看原帖
code厌氧
275822
langligelang楼主2023/5/4 17:19
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 4e5 + 10;

int h[maxn], rep = 1; struct edge{ int to, nx, val, flg;} e[maxn];
void ad(int u, int v, int val){ e[++rep]= {v, h[u], val, 0}, h[u] = rep;}
#define to e[i].to

int n, K;

int rgs[maxn];
int mn, G;

int ans[maxn];

void gt(int x, int fa, int S){
	int mx = 0;
	rgs[x] = 1;
	for (int i = h[x]; i; i = e[i].nx){
		if(to == fa || e[i].flg) continue;
		gt(to, x, S);
		rgs[x] += rgs[to];
		mx = max(mx, rgs[to]);
	}
	mx = max(mx, S - rgs[x]);
	if(mx < mn) mn = mx, G = x;
}

int dis[maxn];

void ins(int x, int fa, int d){
	if(d > K) return;
	dis[d] ++;
	for (int i = h[x]; i; i = e[i].nx){
		if(to == fa || e[i].flg) continue;
		ins(to, x, d+e[i].val);
	}
}

void del(int x, int fa, int d){
	if(d > K) return;
	dis[d] --;
	for (int i = h[x]; i; i = e[i].nx){
		if(to == fa || e[i].flg) continue;
		del(to, x, d+e[i].val);
	}
}


void calc(int x, int fa, int d){
	if(d > K) return;
	
	for (int i = 1; i <= K; i++) {
		if(d > K) continue;
		ans[i] += dis[i - d];
	}
	
	for (int i = h[x]; i; i = e[i].nx){
		if(to == fa || e[i].flg) continue;
		calc(to, x, d+e[i].val);
	}
}

void dfs(int x, int S){
	G = 0; mn = 0x7f7f7f7f7f7f7f7f;
	gt(x, 0, S);
	gt(G, 0, S);
	
	for (int i = h[G]; i; i = e[i].nx){
		if(e[i].flg) continue;
		calc(to, G, e[i].val);
		ins(to, G, e[i].val);
	}
	
	for (int i = 1; i <= K; i++) ans[i] += dis[i];
	
	for (int i = h[G]; i; i = e[i].nx){
		if(e[i].flg) continue;
		del(to, G, e[i].val);
	}
	
	for (int i = h[G]; i; i = e[i].nx){
		if(e[i].flg) continue;
		e[i].flg = 1; e[i^1].flg = 1;
		dfs(to, rgs[to]);
	}
}

#define gc getchar()
int rd(){
	int x = 0; char ch = gc;
	for (; !isdigit(ch); ch = gc);
	for (; isdigit(ch); ch = gc) x = x*10 + ch - '0';
	return x;	
}

signed main(){
	cin >> n;
	for (int i = 1, u, v, val; i < n; i++) u = rd(), v = rd(), val = rd(), ad(u, v, val), ad(v, u, val);
	cin >> K;
	
	dfs(1, n);
	
	int sumans = 0;
	for (int i = 1; i <= K; i++){
		sumans += ans[i];
	}
	
	cout << sumans;
	
	return 0;
}
2023/5/4 17:19
加载中...