当前位置:网站首页>leetcode:6103. 从树中删除边的最小分数【dfs + 联通分量 + 子图的值记录】
leetcode:6103. 从树中删除边的最小分数【dfs + 联通分量 + 子图的值记录】
2022-06-26 21:38:00 【白速龙王的回眸】

分析
显然如果直接遍历两条边 + 里面再dfs会达到三次方,爆裂
因此只能遍历一条边,然后分成两个子树,得到两个异或值tot1和tot2
每个子树我们通过dfs记录这个子树的所有子树的异或值便于分割
然后我们选一颗子树和其中的一个点作为分割点,找完后,一个的分割值是sum1[uu] 另一个就是tot1^sum1[uu]
注意^的性质:0 ^ a = a; a ^ b = c => c ^ b = a
ac code
class Solution:
def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
n = len(nums)
# 特判
if n == 3:
return max(nums) - min(nums)
g = defaultdict(set) # remove faster
for x, y in edges:
g[x].add(y)
g[y].add(x)
# dfs 记录当前以及所有子树的异或值,用xor_sum记录(包含根的)
# 复杂度on
def dfs(p, u, xor_sum):
res = nums[u] # 当前
for v in g[u]:
# 不准回到parent套娃
if v == p:
continue
res ^= dfs(u, v, xor_sum)
# 更新dict
xor_sum[u] = res
return res
res = inf
# 只遍历一条边(2),然后再根据dfs切割子树(3)即可
for i in range(n - 1):
u, v = edges[i]
# cut
g[u].remove(v)
g[v].remove(u)
# 得到两个分别以u和v为根子树对应的异或值和其子树的dict
sum1 = {
}
tot1 = dfs(-1, u, sum1)
sum2 = {
}
tot2 = dfs(-1, v, sum2)
# 如果这两个子树可分,那么继续分
if len(sum1) > 1:
for uu in sum1:
if u == uu:#先当于没砍
continue
x, y, z = sum1[uu], tot1 ^ sum1[uu], tot2
maxn, minn = max(x, y, z), min(x, y, z)
if maxn - minn == 0:
return 0
res = min(res, maxn - minn)
if len(sum2) > 1:
for vv in sum2:
if v == vv:#先当于没砍
continue
x, y, z = sum2[vv], tot2 ^ sum2[vv], tot1
maxn, minn = max(x, y, z), min(x, y, z)
if maxn - minn == 0:
return 0
res = min(res, maxn - minn)
# 回复原样
g[u].add(v)
g[v].add(u)
return res
总结
对于直接无脑找两边tle的情况
可以考虑一条边,然后只有两个子树
但是我们在求其中一个子树的总异或值的时候实际上可以记录这个子树的所有子数的异或值
然后根据异或值的性质,可以快速把这个子树分成两份,这样遍历一条边on,dfs和找子树的点都是on,总的来说就是n方
边栏推荐
- BN(Batch Normalization) 的理论理解以及在tf.keras中的实际应用和总结
- VB.net类库(进阶——2 重载)
- [Shandong University] information sharing for the first and second examinations of postgraduate entrance examination
- leetcode刷题:字符串04(颠倒字符串中的单词)
- Can compass open an account for stock trading? Is it safe?
- Android IO, a first-line Internet manufacturer, is a collection of real questions for senior Android interviews
- 证券注册开户有没有什么风险?安全吗?
- Introduction to dependency injection in SAP Spartacus
- Leetcode question brushing: String 01 (inverted string)
- Matrix derivation and its chain rule
猜你喜欢

VB.net类库——4给屏幕截图,裁剪

Listing of maolaiguang discipline on the Innovation Board: it is planned to raise 400million yuan. Fanyi and fanhao brothers are the actual controllers

关于appium踩坑 :Encountered internal error running command: Error: Cannot verify the signature of (已解决)
![[Shandong University] information sharing for the first and second examinations of postgraduate entrance examination](/img/f9/68b5b5ce21f4f851439fa061b477c9.jpg)
[Shandong University] information sharing for the first and second examinations of postgraduate entrance examination

Kdd2022 𞓜 unified session recommendation system based on knowledge enhancement prompt learning

Dynamic parameter association using postman

Chapter 2 construction of self defined corpus

花店橱窗布置【动态规划】
![[leetcode]- linked list-2](/img/f7/9d4b01285fd6f7fa9f3431985111b0.png)
[leetcode]- linked list-2

VB.net类库(进阶版——1)
随机推荐
网易云信正式加入中国医学装备协会智慧医院分会,为全国智慧医院建设加速...
Configure redis master-slave and sentinel sentinel in the centos7 environment (solve the problem that the sentinel does not switch when the master hangs up in the ECS)
leetcode刷题:字符串04(颠倒字符串中的单词)
Matrix derivation and its chain rule
经典Wide & Deep模型介绍及tensorflow 2代码实现
证券注册开户有没有什么风险?安全吗?
Operator介绍
random_normal_initializer 使用
Is there any risk in opening a mobile stock registration account? Is it safe?
Is there any risk in registering and opening an account for stock speculation? Is it safe?
股票炒股注册开户有没有什么风险?安全吗?
Sword finger offer II 098 Number of paths / Sword finger offer II 099 Sum of minimum paths
[leetcode]- linked list-2
QT based "synthetic watermelon" game
Godson China Science and technology innovation board is listed: the market value is 35.7 billion yuan, becoming the first share of domestic CPU
【protobuf 】protobuf 升级后带来的一些坑
Arrête d'être un bébé géant.
Leetcode(122)——买卖股票的最佳时机 II
网络爬虫终篇:向10万级网易云用户发送定向消息
Usage of MGrid in numpy