题目大意：给你一棵带点权的树，要你求出树上一条链，使得这条链的长度乘上这条链上点权最小值最大
题解：点分，可以求出一个点向下每一条链上最小值以及路径长度，对于一个链的端点，假设到这部分子树的重心距离为$dep$，这条链上最小值为$min$，记录每一个最小值的最长链的长度，可以用树状数组维护最大值（这里是求后缀最大值，所以一次的复杂度还是$O(\log_2n)$），更新答案就行了。
卡点：1.写成了前缀求最大值
2.离散化去重后长度未更改，导致用$lower\_bound$时出锅
C++ Code：
#include#include #include namespace std { struct istream {#define M (1 << 26 | 3) char buf[M], *ch = buf - 1; int f; inline istream() {#ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin);#endif fread(buf, 1, M, stdin); } inline istream& operator >> (int &x) { f = 1; while (isspace(*++ch)); if (*ch == '-') f = -1, ch++; for (x = *ch & 15; isdigit(*++ch); ) x = x * 10 + (*ch & 15); return *this; }#undef M } cin; struct ostream {#define M (1 << 16 | 3) char buf[M], *ch = buf - 1; int w; inline ostream& operator << (int x) { if (!x) { *++ch = '0'; return *this; } if (x < 0) *++ch = '-', x = -x; for (w = 1; w <= x; w *= 10); for (w /= 10; w; w /= 10) *++ch = (x / w) ^ 48, x %= w; return *this; } long long W; inline ostream& operator << (long long x) { if (!x) { *++ch = '0'; return *this; } if (x < 0) *++ch = '-', x = -x; for (W = 1; W <= x; W *= 10); for (W /= 10; W; W /= 10) *++ch = (x / W) ^ 48, x %= W; return *this; } inline ostream& operator << (const char x) {*++ch = x; return *this;} inline ostream& operator << (const char *x) { while (*x) *this << *x++; return *this; } inline ~ostream() {#ifndef ONLINE_JUDGE freopen("output.txt", "w", stdout);#endif fwrite(buf, 1, ch - buf + 1, stdout); }#undef M } cout;}#define maxn 50010const int inf = 0x3f3f3f3f;inline void getmax(int &a, int b) {if (a < b) a = b;}inline void getmax(long long &a, int b) {if (a < b) a = b;}int head[maxn], cnt;struct Edge { int to, nxt;} e[maxn << 1];inline void addedge(int a, int b) { e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt; e[++cnt] = (Edge) {a, head[b]}; head[b] = cnt;}bool vis[maxn];namespace Center_of_Gravity { int sz[maxn], nodenum; int MIN, root;#define n nodenum void __getroot(int u, int fa = 0) { sz[u] = 1; int MAX = 0; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v != fa && !vis[v]) { __getroot(v, u); sz[u] += sz[v]; MAX = std::max(MAX, sz[v]); } } MAX = std::max(MAX, n - sz[u]); if (MAX < MIN) MIN = MAX, root = u; } int getroot(int u, int __nodenum = 0) { n = __nodenum ? __nodenum : sz[u]; MIN = inf; __getroot(u); return root; }#undef n}using Center_of_Gravity::getroot;int n, tot;namespace BIT { int Tr[maxn], res;#define n tot inline void add(int p, const int num) {for (; p; p &= p - 1) getmax(Tr[p], num);} inline int ask(int p) {for (res = -inf; p <= n; p += p & -p) getmax(res, Tr[p]); return res;} inline void clear(int p) {for (; p; p &= p - 1) Tr[p] = -inf;}#undef n}int w[maxn], v[maxn];long long ans;int top;struct List { int tg, dep, min;} S[maxn];void calc() { for (int l = 1, r; l <= top; l = r + 1) { r = l; while (r < top && S[l].tg == S[r + 1].tg) r++; for (int i = l; i <= r; i++) { ans = std::max(ans, static_cast (BIT::ask(S[i].min) + S[i].dep + 1) * v[S[i].min]); } for (int i = l; i <= r; i++) BIT::add(S[i].min, S[i].dep); } for (int i = 1; i <= top; i++) BIT::clear(S[i].min);}void getlist(int u, int tg, int min, int dep = 1, int fa = 0) { min = std::min(min, w[u]); S[++top] = (List) {tg, dep, min}; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v != fa && !vis[v]) getlist(v, tg, min, dep + 1, u); }}void solve(int u) { vis[u] = true; top = 0; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (!vis[v]) getlist(v, v, w[u]); } calc(); std::reverse(S + 1, S + top + 1); calc(); for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (!vis[v]) solve(getroot(v)); }}int main() { std::cin >> n; for (int i = 1; i <= n; i++) { std::cin >> w[i]; getmax(ans, v[i] = w[i]); } tot = (std::sort(v + 1, v + n + 1), std::unique(v + 1, v + n + 1) - v - 1); for (int i = 1; i <= tot; i++) BIT::Tr[i] = -inf; for (int i = 1; i <= n; i++) { w[i] = std::lower_bound(v + 1, v + tot + 1, w[i]) - v; } for (int i = 1, a, b; i < n; i++) { std::cin >> a >> b; addedge(a, b); } solve(getroot(1, n)); std::cout << ans << '\n'; return 0;}