首页 > 其他分享 >权值(点分治)

权值(点分治)

时间:2023-03-23 14:59:20浏览次数:46  
标签:rt maxx int 分治 maxn 权值 节点 dp

264. 权值 - AcWing题库

: \(\color{Yellow}水何澹澹,山岛竦峙。\)

Solution

这是一棵无根树, 所以据此使用点分治。

点分治适合处理大规模的树上路径信息问题。

我们先随意选择一个节点作为根节点 \(\mathit{rt}\),所有完全位于其子树中的路径可以分为两种,一种是经过当前根节点的路径,一种是不经过当前根节点的路径。对于经过当前根节点的路径,又可以分为两种,一种是以根节点为一个端点的路径,另一种是两个端点都不为根节点的路径。而后者又可以由两条属于前者链合并得到。所以,对于枚举的根节点 \(\mathit{rt}\),我们先计算在其子树中且经过该节点的路径对答案的贡献,再递归其子树对不经过该节点的路径进行求解。

-- Oi Wiki

有了这个思路, 我们可以只考虑经过当前子树的的路径,对于新加入的一个子节点信息,我们统计出到达每个节点的距离,并使用dp来维护信息即可。

Attention

点分治的本质是优化暴力                    --Pink Rabit

我们向下递归处理子树时,要找到子树的重心并将其赋为根节点,这样每递归一次,最大的子树大小不超过整棵树大小的一般,最多递归 \(O(logN)\) 层,因此保证了时间复杂度。

时间复杂度 \(O(n \ log \ n)\)

C++ 代码

#include <bits/stdc++.h>
#define for_(i,a,b) for (int i = (a); i < (b); i++)
#define rep_(i,a,b) for (int i = (a); i <= (b); i++)
#define per_(i,a,b) for (int i = (a); i >= (b); i--)
#define ll long long
using namespace std;
const int maxn = 4e5 + 10, mod = 1e9 + 7;// mod = 1949777;
const int inf = 2e9, up = 1e7;
const double EPS = 1e-3;
int n, m, sum;
int tot = 1, rt;
int nxt[maxn], head[maxn], to[maxn], c[maxn];
int q[maxn], sz[maxn], maxx[maxn], vis[maxn], dist[maxn];
void add(int u, int v, int w) {
	nxt[++tot] = head[u]; to[tot] = v; c[tot] = w; head[u] = tot; 
}
void Siz(int u, int fa) {
	sz[u] = 1;
	maxx[u] = 0;
	for (int i = head[u]; i; i = nxt[i]) {
		int v = to[i];
		if (v != fa && !vis[v]) {
			Siz(v, u);
			maxx[u] = max(maxx[u], sz[v]);
			sz[u] += sz[v];
		}
	}
	maxx[u] = max(maxx[u], sum - maxx[u]);
	if (maxx[u] < maxx[rt]) rt = u;
}
int dd[maxn], cnt;
int p[maxn], l[maxn];
void Dist(int u, int D, int fa) {
	dd[++cnt] = D;
	p[u] = p[fa] + 1;
	l[cnt] = p[u];
	for (int i = head[u]; i; i = nxt[i]) {
		int v = to[i];
		if (v != fa && !vis[v]) {
			Dist(v, D + c[i], u); 
		}
	}
}
int k;
int ans = inf;
queue<int> tag;
int dp[up];
void dfs(int u) {
	vis[u] = 1;
	dp[0] = 0;
	tag.push(0);
	for (int i = head[u]; i; i = nxt[i]) {
		int v = to[i];
		if (!vis[v]) {
			cnt = 0;
			Dist(v, c[i], 0);
			for (int j = 1; j <= cnt; j++) {
				if (dd[j] <= k && dp[k - dd[j]] != -1) ans = min(ans, dp[k - dd[j]] + l[j]);
			}
			for (int j = 1; j <= cnt; j++) {
				if (dd[j] <= k) {
					if (dp[dd[j]] == -1 || dp[dd[j]] > l[j]) dp[dd[j]] = l[j], tag.push(dd[j]); 
				}
			}
		}
	}
	while(!tag.empty()) dp[tag.front()] = -1, tag.pop();
	for (int i = head[u]; i; i = nxt[i]) {
		int v = to[i];
		if (!vis[v]) {
			rt = 0; sum = sz[v]; Siz(v, 0); Siz(rt, 0);
			dfs(rt);
		}
	}	
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> k;
	memset(dp, -1, sizeof(dp));
	rep_(i, 1, n - 1) {
		int u, v, w; cin >> u >> v >> w; u++, v++; add(u, v, w); add(v, u, w);
	}
	maxx[0] = inf;
	sum = n;
	rt = 0;
	Siz(1, 0);
	Siz(rt, 0);
	dfs(rt); 
	cout << (ans != inf ? ans : -1) << endl;
	return 0;
}


标签:rt,maxx,int,分治,maxn,权值,节点,dp
From: https://www.cnblogs.com/Cranew/p/17247409.html

相关文章

  • 分治策略
    分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这......
  • CDQ分治
    这是一个比较人类智慧的算法,尽管它大多数时候都不是出题人想要考察的算法,但是绝大部分时候出题人都没办法卡掉你然后愤然强制在线。在怎样的情况下才能使用cdq分治?一般......
  • [学习笔记] CDQ分治
    引入-分治分治,就是将讲原问题不断细分直到规模小到能够解决,然后一层层向上合并得到答案的过程。归并排序大致思想:把序列拆成左右两部分,分别归并排序,然后使用两个指针......
  • Tree Master (根号分治,离散化)
    题目大意:给出一个树,每次给出2个相同高度的点,然后依次向父亲走,问val[a]*val[b]这些值加起来是多少 思路:直接map映射关联容器,时间复杂度过大根号分治?于是......
  • 【洛谷】P2150 [NOI2015] 寿司晚宴(状压dp+根号分治)
    原题链接题意有序列\(2,3,4\cdotsn\),对于序列中的每一个数,它可以被放入两个集合中的任意一个,或者不选。最后需要满足两个集合间的数两两互质(集合内部的数不需要满足互......
  • 分治算法总结(未完结)
    分治思想:将一个问题分解成若干个结构与原问题相同的子问题。(划分子问题+后处理)一、经典问题1.最大子段和思路:计算左边的最大子段和、右边的最大子段和以及跨越......
  • 点分治 学习笔记
    新知识+1。0x00前言点分治适合处理大规模的树上路径信息问题。0x01引入我们通过洛谷的模板题来引入点分治的概念:P3806【模板】点分治1:给定一棵有n个点的带边......
  • 分治
    乘法的优化暴力的乘法复杂度是\(O(n^2)\)的。如果两个\(n\)位数\(x,y\)相乘(我们保证\(n\)是2的幂),那么我们按位把\(x\)分成\(x_L,x_R\)两半,\(y\)分成\(y_L,y_R\),使得\(x=x......
  • 快速幂——分治思想
    问题:求解pow(x,n)解题思路:1.将n个x相乘,时间复杂度为O(n)2.分治思想:二进制数转化成10进制数的方法:二进制数为n=2k-1 *ak  + 2k-2*ak-1+......
  • 【算法设计-分治】递归与尾递归
    目录1.阶乘尾递归:递归的进一步优化2.斐波那契数列3.最大公约数(GCD)4.上楼梯5.汉诺塔(1)输出移动过程输出移动步数5.汉诺塔(2)输出移动过程输出移动步数6.杨辉三角形7.完......