MnZn刚学点分治1秒,样例输出-1求调
查看原帖
MnZn刚学点分治1秒,样例输出-1求调
503792
Svemit楼主2023/2/3 10:06

rt

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long ull;
const int N = 4e4 + 5, INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;

int n, k;
bool st[N];
int p[N], q[N];
struct edge
{
	int v, w;
};
std::vector<edge> e[N];

int get_siz(int u, int fa)
{
	if(st[u]) return 0;
	int res = 1;
	for(auto i:e[u])
	{
		int v = i.v;
		if(v == fa) continue;
		res += get_siz(v, u);
	}
	return res;
}

int get_root(int u, int fa, int tot, int &rt)
{
	if(st[u]) return 0;
	int siz = 1, ms = 0;
	for(auto i:e[u])
	{
		int v = i.v;
		if(v == fa) continue;
		int t = get_root(v, u, tot, rt);
		ms = max(ms, t);
		siz += t;
	}
	ms = max(ms, tot - siz);
	if(ms <= tot / 2) rt = u;
	return siz;
}

void get_dis(int u, int fa, int dis, int &qt)
{
	if(st[u]) return;
	q[qt ++] = dis;
	for(auto i:e[u])
	{
		int v = i.v, w = i.w;
		if(v == fa) continue;
		get_dis(v, u, dis + w, qt);
	}
}

int solve(int d[], int len, int m)
{
	sort(d, d + len);
	int res = 0;
	for(int i = len - 1, j = -1;i >= 0;i --)
	{
		while(j + 1 < i && d[j + 1] + d[i] <= m) j ++;
		j = min(j, i - 1);
		res += j + 1;
	}
	return res;
}

int calc(int u)
{
	if(st[u]) return 0;
	int res = 0;
	get_root(u, 0, get_siz(u, 0), u);
	st[u] = true;
	int pt = 0;
	for(auto i:e[u])
	{
		int v = i.v, w = i.w, qt = 0;
		get_dis(v, 0, w, qt);
		res -= solve(q, qt, k);
		for(int j = 0;j < qt;j ++)
		{
			if(q[j] <= k) res ++;
			p[pt ++] = q[j];
		}
	}
	res += solve(p, pt, k);
	for(auto i:e[u]) res += calc(i.v);
	return res;
}

int main()              //主函数
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for(int i = 1;i < n;i ++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		e[u].push_back({v, w});
		e[v].push_back({u, w});
	}
	cin >> k;
	cout << calc(1) << '\n';
    return 0;
}
2023/2/3 10:06
加载中...