3

SPOJ COT6. Cut on a tree

 3 years ago
source link: http://www.shuizilong.com/house/archives/spoj-cot6/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
September 9, 2021

前排膜拜主席。。。

做了好几天。。总算搞定了。。

DP 结构和 COT3 一样，方程和 Cash 一样，都是动态维护凸壳，询问与某个向量的点积的最小值。。。
后来我系统的学习了一下 线段树合并，
然后发现有一个题的做法是李超线段树 + 线段树合并，来搞树上 dp。。。

这个题的方程和那个题差不多。。。询问向量都是 (x, 1)，所以用 kx+b 来搞更方便。。。
可以预处理出所有的 sw，来做离散化，然后打标记只要整体平移 b，不会影响线段树的结构。。。
然后就没有然后了。。。复杂度 O(nlog2n)。。。

经过这个题我们发现。。线性分段函数极值 和 动态凸包 问题是等价的。。
根据情况可以互相转换。。看怎么写好写。。。

似乎还有一种 O(nlogn) 的做法。。。dfs 序 + cdq 分治。。。
晚上再试试。。。

我发现之前的模板里有一个 bug 的地方（我靠居然连 COT6 的样例都过不去。。）

if (T[x].y(ml) > t.y(ml) || T[x].y(mr) > t.y(mr)) swap(T[x], t); //!

就是上面这行，必须要两边都检查一次，否则有可能恰好在边界，然后又相等的话，我这种写法就炸了。。。。

const int N = int(1.2e6) + 9;
const int NN = N * 20;
int n;
VI adj[N]; LL sw[N], dp[N];
vector<LL> P;
struct Line {
static int x;
LL k,b;
Line(){}
Line(LL k, LL b):k(k),b(b){
}
LL y(int x = Line::x) const {
return k*P[x]+b;
}
};
int Line::x;
namespace Chairman_Tree {
#define lx c[0][x]
#define rx c[1][x]
#define ly c[0][y]
#define ry c[1][y]
#define ml ((l+r)>>1)
#define mr (ml+1)
#define lc lx, l, ml
#define rc rx, mr, r
int c[2][NN]; int tot; LL b[NN];
Line T[NN], t;
int new_node() {
return ++tot;
}
void up(int x, LL d) {
T[x].b += d;
b[x] += d;
}
void rls(int x) {
if (b[x]) {
up(lx, b[x]); up(rx, b[x]);
b[x] = 0;
}
}
void Insert(int &x, int l, int r, Line t) {
if (!x) {
T[x = new_node()] = t;
return;
}
if (T[x].y(ml) > t.y(ml) || T[x].y(mr) > t.y(mr)) swap(T[x], t); //!
if (l == r || sgn(t.y(l)-T[x].y(l)) * sgn(t.y(r)-T[x].y(r)) >= 0)   return;
rls(x);
Insert(lc, t);
Insert(rc, t);
}
int Merge(int x, int y, int l = 0, int r = SZ(P)-1) {
if (!x || !y) return x | y;
Insert(x, l, r, T[y]);
rls(x); rls(y);
lx = Merge(lx, ly, l, ml);
rx = Merge(rx, ry, mr, r);
return x;
}
LL Query(int x, int l = 0, int r = SZ(P)-1) {
if (!x) return INFF;
rls(x);
return min(T[x].y(), Line::x < mr ? Query(lc) : Query(rc));
}
} using namespace Chairman_Tree;
int rt[N];
void dfs0(int u,int p) {
sw[u] += sw[p];
for (auto v: adj[u]) if (v != p) {
dfs0(v, u);
}
P.PB(-2*sw[p]);
}
void dfs(int u,int p) {
LL s = 0;
for (auto v: adj[u]) if (v != p) {
dfs(v, u);
s += dp[v];
}
Insert(rt[u], 0, SZ(P)-1, Line(sw[u], s + sqr(sw[u])));
for (auto v: adj[u]) if (v != p) {
up(rt[v], s - dp[v]);
rt[u] = Merge(rt[u], rt[v]);
}
Line::x = LBD(P, -2*sw[p]);
dp[u] = sqr(sw[p]) + Query(rt[u]);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
RD(n); REP_1(i, n) RDD(sw[i]);
DO(n-1) {
int u, v; RD(u, v);
adj[u].PB(v);
adj[v].PB(u);
}
dfs0(1, 0); UNQ(P);
dfs(1,0);
OT(dp[1]);
}

Posted by xiaodao
Category: 日常


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK