工大最菜
工大最菜
全部文章
树形dp
01规划(3)
ACM比赛总结(3)
ACM训练日记(11)
bfs(7)
dfs(5)
Dilworth定理(1)
dp(80)
exgcd(1)
gcd(2)
java(1)
KM(1)
kmp(4)
map(4)
MOD运算(1)
os(3)
rmq(1)
set(2)
STL的操作(1)
__int128(1)
一般图带花树的最大匹配(2)
三分(2)
中位数(1)
主席树(6)
二分(8)
二分图匹配(9)
二分图最大匹配(1)
二分图的多重匹配(1)
二维偏序(2)
二进制(2)
优先队列(2)
倍增DP(2)
其他(1)
分块(11)
分层图最短路(1)
分治(5)
分组背包(3)
前缀和(6)
动态最短路(1)
区间dp(18)
单调队列(2)
单调队列dp(2)
博弈论(11)
双连通(5)
同余最短路(1)
后缀和(1)
后缀数组(2)
因数(1)
大整数(1)
大模拟(2)
字典树(1)
字符串哈希(16)
完全背包(1)
容斥(1)
尺取(4)
并查集(3)
序列自动机(2)
康托展开(1)
异或(4)
强连通(1)
思维(6)
扩展KMP(3)
扫描线(2)
技巧(11)
拉格朗日插值法(1)
拓扑排序(3)
数位dp(8)
数学推导(2)
数论(18)
整体二分(2)
暴力(6)
最大权闭合子图(1)
最小生成树(5)
最小表示法(1)
最短路(15)
未归档(2)
构造(2)
构造树(1)
染色问题(1)
树(9)
树dfs序(2)
树上分块(2)
树上启发式合并(6)
树上差分(2)
树状数组(3)
树的BFS序(1)
树链剖分(6)
概率(24)
模拟退火(6)
欧拉函数(3)
欧拉回路(4)
点分治(5)
状压dp(11)
珂朵莉树(2)
生成函数(4)
矩阵快速幂(3)
矩阵计数(1)
离散数学(1)
离线(1)
线性基(1)
线性规划(1)
线段树(18)
线段树合并(2)
组合数学(1)
组合计数(1)
网络流(14)
莫比乌斯反演(1)
莫队(6)
表达式求值(1)
计数(5)
计算几何(4)
调度问题(1)
贪心(8)
费用流(6)
费用背包(1)
递归(2)
长链剖分(1)
题解(14)
归档
标签
去牛客网
登录
/
注册
liweihang的博客
全部文章
/ 树形dp
(共16篇)
每日一题 7月13日 Kingdom 两个树形DP
题目链接:https://ac.nowcoder.com/acm/problem/19810题目大意:思路:我们定义DP[i]:i个节点形成的树的最大花费。我们知道重儿子是一个费用的影响因素:那么我们枚举重儿子的节点个数为x。因为除了重儿子,其他节点到根都有费用。DP[i]=max(DP[i], D...
2020-07-16
0
491
2019 icpc 上海站 H Tree Partition 树形DP
题目链接:https://ac.nowcoder.com/acm/contest/6234/H题目大意:有一棵n节点的树,每个节点上有权值,希望你把他的k-1条边拆开。形成k棵子树,每棵树的权值为节点权值的和。问这k棵子树的最大权值最小为多少? 思路:二分,然后我们思考,对于一个节点,他会和若干子节...
2020-07-04
0
627
每日一题 6月18日 颓红警 树形DP-维护区间平方差距离
题目链接:https://ac.nowcoder.com/acm/problem/19314题目大意:就是有一棵树,每个节点有一个防御力mi[i], 你的攻击力为P,你1是根节点,每次你可以选择一个节点i进行攻击,对i造成的伤害为P,对i的子孙j造成 的伤害,并且攻击i节点时,保证他的所有祖先全部被...
2020-06-20
0
704
学军信友队趣味网络邀请赛 A-B-D 思维+树形DP/直径+数论
题目链接:http://115.236.49.52:83/contest/1351A题:题解:假设n是奇数。n如果是偶数,翻转90度就可以了。 B题: #include <bits/stdc++.h> using namespace std; #define LL long long...
2020-04-06
0
629
poj1947 Rebuilding Roads - 树上背包-删除最少边得到一个大小为p的连通块
题目链接:http://poj.org/problem?id=1947 题目大意:一棵节点数为n的树。让你删除最少的边。得到一个大小为p的子树。 p<=n<150。 我 ...
2020-02-28
0
517
省赛E-树形dp计数-换根+二次扫描
昨晚上学了二次扫描后,才发现省赛的树形dp题竟然可以用这个写。 我们用f[u] 表示:以节点u为根的递增路径条数。并且计算这些路径相互之间的贡献。 void dfs1(int u, int fa){ for(int i=0; i<v[u].size(); i++){ ...
2019-12-05
0
464
最大疯子树-树形dp+换根+二次扫描
分析: 疯子树肯定还是一棵树。 所以,所谓的最短路径就是吓唬你的,树上两点之间有且只有一条路径。 b1和b2必须是相邻的,否则不可能是一棵疯子树。 再想一想,用同样的方式构造剩下的点的话,那么可以得到一个结论: 如果以一棵疯子树以键值最小的那个节点为根,那么对于从根到叶的每一条简单路径上,键值是不...
2019-12-05
0
496
CCF 201909-5 城市规划-树形dp
题目链接;http://www.freesion.com/article/8602142306/ 题目大意: 思路: u是v的直连父亲,先往下搜,向上回溯时, 枚举边计算贡献,即u和v之间边w,v里面选了p个,则all-v这一块选k-p个 边w被经过p*(k-p)次, 实际转移时,考虑v里...
2019-12-04
0
722
codeforces 1244 D - Paint the Tree 树链上dp
题目链接:http://codeforces.com/contest/1244/problem/D 题目大意:给你一棵树,让你染色,一共有3种颜色.i节点涂成颜色1代价为a[i], 2:b[i], 3:c[i]。 并且树一条路径上连续的三个节点不能有颜色重复。 输出最小代价,或者不能做到-1。 ...
2019-11-20
0
475
树形dp-UVA-12186-工人***书
题目链接:https://vjudge.net/contest/307650#problem/A 题目大意: 思路: 设d(u)表示让u给上级发信最少需要多少个工人。假设u有k个子结点,则至少需要c=kT/100+(kT%100==0?0:1)个直接下属发信才行。把所有子结点的d值从小到大...
2019-10-18
0
499
首页
上一页
1
2
下一页
末页