@codechef - KILLER@ Painting Tree
2024-09-06 13:15:20
@description@
给定一个 N 个点的有根树，标号 1 到 N，以 1 为根。定义一个结点 x 的深度 dep[x] 为 x 到根经过的边的数量。
将整棵树剖分成若干竖直的链（链上结点总是由祖先到后代），每条竖直的链的代价如下：
\[\sum_w(C[u] \times (h - dep[w]) + C[u]^2) - H[u]
\]
\]
其中 u 是链的最低点，w 是链上的点，h 为整棵树最深的点的深度，C, H 为给定的数组。
求整棵树的一个剖分方案，使得链的代价和最小。输出最小代价和。
@solution@
考虑把链的代价函数化简，得到较为简洁的表示。
注意到 dep[w] 是一个，所以求和部分实际上可以写成 C[u] 乘上等差数列求和。
设 x 为最高点，则最终一条链的代价可以记作 \(a(u) \times dep^2[x] + b(u) \times dep[x] + c(u)\)。
其中 \(a(u) = C[u], b[u] = C[u]^2 + C[u]\)，剩下 c(u) 太长了就不写了。
可以作一个 O(n^2) 的 dp，对于每个 x 枚举它所在链的最低点是哪个点，记作 u。
然后转移时除了自己这条链的代价，还要加上删去自己这条链过后其余子树的 dp 值之和。
注意到我们可以使用线段树合并快速维护 “删去某个点 u 到根 x 这条链过后其余子树的 dp 值之和”。
感觉 dp 推不动了？试试决策单调性。
注意到该二次函数的对称轴 \(x = -\frac{C[u]^2 + C[u]}{2C[u]} = -\frac{C[u] + 1}{2}\) 始终 < 0，而 dep[x] 始终 >= 0。
这意味着其实二次函数并不是完整的二次函数，只是二次函数的右半部分。但还是不好维护。
注意我们维护一次函数（斜率优化）时，除了传统的凸包维护以外，还可以用神奇的李超线段树维护。
这道题其实也可以用李超线段树，因为它满足李超线段树所要求的单调性（不好描述。。。反正正确性挺显然的）。
所以直接上李超线段树的树上线段树合并即可。
@accepted code@
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 100000;
const ll INF = (1LL << 60);
struct edge{
edge *nxt; int to;
}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt;
void addedge(int u, int v) {
edge *p = (++ecnt);
p->to = v, p->nxt = adj[u], adj[u] = p;
p = (++ecnt);
p->to = u, p->nxt = adj[v], adj[v] = p;
}
int dep[MAXN + 5], mxd, N;
ll C[MAXN + 5], H[MAXN + 5];
void init() {
ecnt = edges;
for(int i=1;i<=N;i++)
adj[i] = NULL;
}
ll dp[MAXN + 5], s[MAXN + 5];
ll a(int u) {return C[u];}
ll b(int u) {return 2*C[u]*C[u] + C[u];}
ll c(int u) {return C[u]*(C[u] + dep[u] + C[u])*(1 - dep[u]) - 2*H[u];}
struct func{
ll a, b, c;
func(ll _a=0, ll _b=0, ll _c=0) : a(_a), b(_b), c(_c) {}
ll get(ll x) {return (a*x + b)*x + c;}
};
struct segtree{
struct node{
func f; ll tg;
node *ch[2];
}pl[20*MAXN + 5], *ncnt, *NIL;
void clear() {
NIL = ncnt = pl;
NIL->ch[0] = NIL->ch[1] = NIL;
}
void maintain(node *x, ll k) {
x->tg += k, x->f.c += k;
}
void pushdown(node *x) {
if( x->tg ) {
if( x->ch[0] != NIL ) maintain(x->ch[0], x->tg);
if( x->ch[1] != NIL ) maintain(x->ch[1], x->tg);
x->tg = 0;
}
}
node *newnode(func f) {
node *p = (++ncnt);
p->ch[0] = p->ch[1] = NIL;
p->f = f, p->tg = 0;
return p;
}
void insert(node *&x, int l, int r, func f) {
if( x == NIL ) {
x = newnode(f);
return ;
}
pushdown(x);
if( x->f.get(l) > f.get(l) )
swap(x->f, f);
int m = (l + r) >> 1;
if( x->f.get(m) > f.get(m) )
swap(x->f, f), insert(x->ch[0], l, m, f);
else if( x->f.get(r) > f.get(r) )
insert(x->ch[1], m + 1, r, f);
}
node *merge(node *x, node *y, int l, int r) {
if( x == NIL ) return y;
if( y == NIL ) return x;
pushdown(x), pushdown(y);
int m = (l + r) >> 1;
x->ch[0] = merge(x->ch[0], y->ch[0], l, m);
x->ch[1] = merge(x->ch[1], y->ch[1], m + 1, r);
insert(x, l, r, y->f);
return x;
}
ll query(node *x, int l, int r, int p) {
if( x == NIL ) return INF;
int m = (l + r) >> 1;
pushdown(x);
if( p <= m ) return min(query(x->ch[0], l, m, p), x->f.get(p));
else return min(query(x->ch[1], m + 1, r, p), x->f.get(p));
}
}T;
segtree::node *rt[MAXN + 5];
void dfs(int x, int f) {
s[x] = 0;
for(edge *p=adj[x];p;p=p->nxt) {
if( p->to == f ) continue;
dfs(p->to, x), s[x] += dp[p->to];
}
rt[x] = T.newnode(func(a(x), b(x), c(x) + s[x]));
for(edge *p=adj[x];p;p=p->nxt) {
if( p->to == f ) continue;
T.maintain(rt[p->to], s[x] - dp[p->to]);
rt[x] = T.merge(rt[x], rt[p->to], 0, mxd);
}
dp[x] = T.query(rt[x], 0, mxd, dep[x]);
}
void get_dep(int x, int f) {
dep[x] = dep[f] + 1;
for(edge *p=adj[x];p;p=p->nxt) {
if( p->to == f ) continue;
get_dep(p->to, x);
}
mxd = max(mxd, dep[x]);
}
void solve() {
scanf("%d", &N), init();
for(int i=1;i<=N;i++)
scanf("%lld%lld", &H[i], &C[i]);
for(int i=1;i<N;i++) {
int u, v; scanf("%d%d", &u, &v);
addedge(u, v);
}
mxd = dep[0] = -1, get_dep(1, 0);
for(int i=1;i<=N;i++) dep[i] = mxd - dep[i];
T.clear(), dfs(1, 0);
printf("%lld\n", dp[1] / 2);
}
int main() {
int T; scanf("%d", &T);
while( T-- ) solve();
}
@details@
从这道题也可以看出，具有决策单调性的 dp 其实也可以使用李超线段树来维护。
感觉李超线段树挺好用的.jpg。平衡树维护凸包是什么啊，丢了丢了。
最新文章
- 了解HTML图像
- 初学者--bootstrap（五）JavaScript插件（上）----在路上（6）
- 15 Best Responsive HTML5 Frameworks 2014
- [转载]Python-第三方库requests详解
- SQL实现将一个表的数据插入到另外一个表的代码
- 报错：java.io.FileNotFoundException: (系统找不到指定的路径。)
- Motan学习开篇
- linux 命令学习（4）
- Typefaces and Personalities (字体与性格)
- cocos2d-x项目过程记录(Objective-C转C++)
- 《学习opencv》笔记——矩阵和图像操作——cvCalcCovarMatrix,cvCmp and cvCmpS
- 1.padding和margin，几种参数
- 初探原生js根据json数据动态创建table
- MAP--复杂map结构的构造
- 一个技术汪的开源梦 —— 微信开发工具包（WeixinSDK）
- PHP运行出现Notice : Use of undefined constant
- MySQL （六）--外键、联合查询、子查询
- 关于Linux虚拟化技术KVM的科普
- Mysql [Err] 1292 - Truncated incorrect DOUBLE value
- django models返回数据根据某字段倒序排列