首页 > 最大稳定数值
开通博客写题解
头像 AliLexiWalker
发表于 2026-04-18 00:23:20
先把每个点从根到它的和、整棵子树的和预处理出来，先算一遍不删边时的支撑点总数。然后再跑一遍非递归DFS，用树状数组维护祖先里哪些点会因为“删掉当前子树”而变成支撑点，最后每条边都按删前总数-被删子树里的支撑点+新变成的支撑点算一下，取最大值。 void solve(){ int n;cin& 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 此在Dasein
发表于 2026-04-18 05:06:46
一、 问题分析 本题的核心在于维护两个动态约束条件。对于任意结点 ： 上层约束 (Ancestors Condition)：其所有严格祖先结点的权值之和 。 下层约束 (Descendants Condition)：其所有严格子孙结点的权值之和 。 关键性质观察： 上层约束的静态性：删除以 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 腌萝卜干
发表于 2026-04-19 14:55:40
贴个代码吧 #include <bits/stdc++.h> #define x first #define y second #define all(x) x.begin(), x.end() #define vec1(T, name, n, val) vector<T> 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 星夜c
发表于 2026-04-18 01:04:40
#include <iostream> #include <vector> #include <algorithm> #include <functional> using namespace std; typedef long long ll; 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 BaiJay
发表于 2026-04-20 20:14:32
总结：三个dfs搜索，一个离散化处理，一个权值树状数组即可解决此问题 #include <bits/stdc++.h> #define int long long #define vi vector<int> #define vii vector<vector<i 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”