题意：给定树，有点权。求一条路径使得最小点权 * 总点数最大。只需输出这个最大值。5w。
解：树上路径问题，点分治。
考虑合并两个子树的时候，答案的形式是val1 * (d1 + d2)，当1是新插入的节点的时候，只需在val比它大的点中选出一个最大的d2，这树状数组就可以做到。
当2是新插入的节点时候，好像需要凸包了？但是我们完全不虚啊，因为我们倒序枚举子树就能让2在1之前插入。
于是正反枚举两次子树，拿树状数组维护一下后缀最大值就行了。
复杂度O(nlog2n)
/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/ #include <bits/stdc++.h> #define forson(x, i) for(int i = e[x]; i; i = edge[i].nex) typedef long long LL;
const int N = , INF = 0x3f3f3f3f; struct Edge {
int nex, v;
}edge[N << ], edge2[N << ]; int tp, tp2; int e[N], n, siz[N], _n, root, small, e2[N], xx, d[N], Val[N];
LL val[N], X[N], ans;
bool del[N]; inline void add(int x, int y) {
tp++;
edge[tp].v = y;
edge[tp].nex = e[x];
e[x] = tp;
return;
} inline void add2(int x, int y) {
tp2++;
edge2[tp2].v = y;
edge2[tp2].nex = e2[x];
e2[x] = tp2;
return;
} namespace ta {
int ta[N];
inline void add(int x, int v) {
x = xx + - x;
for(int i = x; i <= xx; i += i & (-i)) {
ta[i] = std::max(ta[i], v);
}
return;
}
inline void del(int x) {
x = xx + - x;
for(int i = x; i <= xx; i += i & (-i)) {
ta[i] = -INF;
}
return;
}
inline int getMax(int x) {
x = xx + - x;
int ans = -INF;
for(int i = x; i; i -= i & (-i)) {
ans = std::max(ans, ta[i]);
}
return ans;
}
} void getroot(int x, int f) {
siz[x] = ;
int large = ;
forson(x, i) {
int y = edge[i].v;
if(y == f || del[y]) continue;
getroot(y, x);
siz[x] += siz[y];
if(siz[y] > large) {
large = siz[y];
}
}
if(_n - siz[x] > large) {
large = _n - siz[x];
}
if(small > large) {
small = large;
root = x;
}
return;
} void DFS_1(int x, int f) {
siz[x] = ;
d[x] = d[f] + ;
Val[x] = std::min(Val[f], (int)val[x]);
ans = std::max(ans, X[Val[x]] * (d[x] + ta::getMax(Val[x])));
forson(x, i) {
int y = edge[i].v;
if(del[y] || y == f) continue;
DFS_1(y, x);
siz[x] += siz[y];
}
return;
} void DFS_2(int x, int f) {
ta::add(Val[x], d[x] + );
forson(x, i) {
int y = edge[i].v;
if(y == f || del[y]) continue;
DFS_2(y, x);
}
return;
} void DFS_3(int x, int f) {
ta::del(Val[x]);
forson(x, i) {
int y = edge[i].v;
if(del[y] || y == f) {
continue;
}
DFS_3(y, x);
}
return;
} void poi_div(int x) {
small = INF;
getroot(x, );
x = root; d[x] = ;
Val[x] = val[x];
ta::add(Val[x], );
forson(x, i) {
int y = edge[i].v;
if(del[y]) continue;
DFS_1(y, x);
DFS_2(y, x);
}
DFS_3(x, );
// ---------
for(int i = e2[x]; i; i = edge2[i].nex) {
int y = edge2[i].v;
if(del[y]) continue;
DFS_1(y, x);
DFS_2(y, x);
}
ans = std::max(ans, X[val[x]] * ta::getMax(val[x]));
DFS_3(x, ); del[x] = ;
forson(x, i) {
int y = edge[i].v;
if(del[y]) continue;
_n = siz[y];
poi_div(y);
}
return;
} int main() { scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%lld", &val[i]);
X[i] = val[i];
}
std::sort(X + , X + n + );
xx = std::unique(X + , X + n + ) - X - ;
for(int i = ; i <= n; i++) {
val[i] = std::lower_bound(X + , X + xx + , val[i]) - X;
}
ans = X[xx];
for(int i = , x, y; i < n; i++) {
scanf("%d%d", &x, &y);
add(x, y); add(y, x);
}
for(int x = ; x <= n; x++) {
forson(x, i) {
add2(x, edge[i].v);
}
} poi_div(); printf("%lld\n", ans);
return ;
}
AC代码
题外话：感觉能树形DP，但是要线段树合并 + 凸包合并，虚的一批...
还发现了一个O(nlogn)的做法，只需多叉转二叉然后O(n) - O(1)lca即可实现，瓶颈在于排序...
然而这题是边分治模板题...