人调麻了,求助(代码含注释)
查看原帖
人调麻了,求助(代码含注释)
748239
OIbishop楼主2023/12/10 20:11
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
struct node {int to , w;};
vector < node > e[N];
struct edge {int u , v , w;} a[N];
int n , k , fa[N] , d[N] , dis[N] , tot , pos1 , pos2 , dep[N] , maxn = INT_MIN;
bool vis[N]; int sum[N] , s , len[N];
void dfs (int u , int f)
{
	for (auto v : e[u])
	{
		if (v.to == f) continue;
		dis[v.to] = dis[u] + v.w;
		dfs (v.to , u);
	}
} // 树的直径dfs 
void calc (int u , int f) {fa[u] = f; dep[u] = dep[f] + 1; for (auto v : e[u]) {if (v.to == f) continue; calc (v.to , u);}}
// calc预处理父亲和深度 
void init (int u , const int root)
{
	for (auto Node : e[u])
	{
		int v = Node.to , w = Node.w;
		if (vis[v]) continue;
		d[v] = d[u] + w;
		init (v , root);
	}
	len[root] = max (len[root] , d[u]);
}
// d[i]代表i节点到根的距离,len就是离根最远的距离,此处处理直径上每一个点的子树中离它最远的距离 
map < pair <int , int> , int> mp; // mp[{i , j}]代表i节点到j节点的距离 
vector <int> lin , lin__;// lin存直径 
int f[N << 2] , id[N];// f是线段树数组,id[i]代表直径上的第i个点的编号 
#define ls (o << 1)
#define rs (o << 1 | 1)
inline void build_tree (int o , int l , int r)
{
	if (l == r) 
		return f[o] = len[id[l - 1]] , void ();
	int mid = l + r >> 1;
	build_tree (ls , l , mid);
	build_tree (rs , mid + 1 , r);
	f[o] = max (f[ls] , f[rs]); 
}
inline int query (int o , int l , int r , int x , int y)
{
	if (l > r) return INT_MIN;
	if (l == x && r == y)
		return f[o];
	int mid = l + r >> 1;
	if (y <= mid)
		return query (ls , l , mid , x , y);
	else if (x > mid)
		return query (rs , mid + 1 , r , x , y);
	else 
		return max (query (ls , l , mid , x , mid) , query (rs , mid + 1 , r , mid + 1 , y));
}// 线段树维护区间len的最大值 ,也就是直径上的点的子树内离它最远的距离 
signed main ()
{
	cin >> n >> s;
	for (int i = 1; i < n; i++)
	{
		int u , v , w;
		cin >> u >> v >> w;
		mp[make_pair (u , v)] = mp[make_pair (v , u)] = w;
		e[u].push_back ((node){v , w});
		e[v].push_back ((node){u , w});
	}
	dfs (1 , 0);
	for (int i = 1; i <= n; i++)
		if (dis[i] > dis[pos1]) pos1 = i;
	memset (dis , 0 , sizeof dis);
	dfs (pos1 , 0);
	for (int i = 1; i <= n; i++)
		if (dis[i] > dis[pos2]) pos2 = i;
	memset (dis , 0 , sizeof dis); // pos1,pos2是直径上的两个端点 
	calc (1 , 0);
	int x = pos1 , y = pos2;
	while (x ^ y) // 这里就是x != y的意思 
	{
		if (dep[x] < dep[y])
			x ^= y ^= x ^= y; // 这里相当于swap 
		x = fa[x];
	}//暴力跳lca 
	int lca = x;
	x = pos1;
	while (x ^ lca)
	{
		lin.push_back (x);
		x = fa[x];
	}//记录pos1到lca路径上的节点 
	lin.push_back (lca);
	y = pos2;
	while (y ^ lca)
	{
		lin__.push_back (y);
		y = fa[y];
	}
	reverse (lin__.begin () , lin__.end ());
	for (auto i : lin__)
		lin.push_back (i);
	//以上就是记录直径 
	for (auto i : lin) vis[i] = true;
	int totnode = 0;
	for (auto i : lin)
		init (i , i) , id[++totnode] = i; // 预处理直径上的每一个节点的子树内的最远距离 
	int lstnode = lin[0];
	build_tree (1 , 1 , totnode);//totnode就是有几个节点 
	int l = 0 , r = 0 , lt = 0 , rt = 0 , res = INT_MAX;
	for (int i = 1; i < lin.size (); i++)
		sum[i] = sum[i - 1] + mp[{lstnode , lin[i]}], // sum就是统计直径上的前缀和 
		lstnode = lin[i];
	//lt是距离直径的左端点的最远距离,rt就是右端点的最远距离,l和r就是双指针 
    rt = sum[lin.size () - 1];
	for (r = 1; r < lin.size (); ++r , rt -= mp[{lin[r - 1] , lin[r]}])
	{
		while (sum[r] - sum[l] > s)
			l++ , lt += mp[{lin[l - 2] , lin[l - 1]}];
//		cout << l << " " << r << " " << totnode << "\n";
//        cout << lt << " " << rt << " " << query (1 , 1 , totnode , l , r) << " " << l << " " << r << "\n";
		res = min (res , max ({lt , rt , query (1 , 1 , totnode , l , r)}));
		//就是正常的双指针 
	}
	cout << res;
	return 0;
}
2023/12/10 20:11
加载中...