CF1088F. Ehab and a weird weight formula

Solution

這題大概是個大力找性質(zhì)題（莫名感覺學(xué)習(xí)文化課有利于找性質(zhì)？！？）。

性質(zhì)1：不難發(fā)現(xiàn)一個點比它權(quán)值小的有且僅有一個（最小權(quán)點除外）

性質(zhì)2：我們把最小權(quán)點作為根，原樹形成一個小根堆。

點和邊都有貢獻顯然很難受。我們把點的貢獻移到邊上，于是邊的貢獻變成：
$$?lo{g}_{2}dis(u,v)?\times min(a_u,a_v)+a_u+a_v$$
設(shè)一個點$x$在原樹上比它權(quán)值小的點編號為$i{d}_x$。

性質(zhì)3：新樹上一個點只會選擇權(quán)值比它小的點作為$father$。（不然還不如選$i{d}_x$，貢獻為$a_{i{d}_x}$+$a_x$）

性質(zhì)4：因此設(shè)當(dāng)前要選擇$x$在新樹上的$father$，發(fā)現(xiàn)只可能在原樹上$i{d}_x$到根的路徑上，也就是原樹上$x$的父親到根的路徑上（不然不如取這個點和$x$的$LCA$）。

然后對于形如$?log(dis(x,y))?$的式子，顯然是把$x$到根的鏈分成$O(log)$段，每段的$?log(dis(x,y))?$相等，由于小根堆的性質(zhì)，我們只會取每一段的最上面的點。

于是倍增維護一下祖先，$O(logn)$跳鏈即可。

總時間復(fù)雜度$O(nlgn)$。

Code

#include <bits/stdc++.h>using namespace std;template<typename T> inline bool upmin(T &x, T y) { return y < x ? x = y, 1 : 0; } template<typename T> inline bool upmax(T &x, T y) { return x < y ? x = y, 1 : 0; }#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondtypedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int, int> PR; typedef vector<int> VI; const lod eps = 1e-9; const lod pi = acos(-1); const int oo = 1 << 30; const ll loo = 1ll << 60; const int mods = 998244353; const int inv2 = (mods + 1) >> 1; const int MAXN = 300005; const int INF = 0x3f3f3f3f; //1061109567 /*--------------------------------------------------------------------*/namespace FastIO{constexpr int SIZE = (1 << 21) + 1;int num = 0, f;char ibuf[SIZE], obuf[SIZE], que[65], *iS, *iT, *oS = obuf, *oT = obuf + SIZE - 1, c;#define gc() (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)), (iS == iT ? EOF : *iS ++)) : *iS ++)inline void flush() {fwrite(obuf, 1, oS - obuf, stdout);oS = obuf;}inline void putc(char c) {*oS ++ = c;if (oS == oT) flush();}inline void getc(char &c) {for (c = gc(); !isdigit(c) && c != EOF; c = gc());}inline void reads(char *st) {char c;int n = 0;getc(st[++ n]);for (c = gc(); isdigit(c) ; c = gc()) st[++ n] = c;st[n + 1] = '\0';}template<class I>inline void read(I &x) {for (f = 1, c = gc(); c < '0' || c > '9' ; c = gc()) if (c == '-') f = -1;for (x = 0; c >= '0' && c <= '9' ; c = gc()) x = (x << 3) + (x << 1) + (c & 15);x *= f;}template<class I>inline void print(I x) {if (x < 0) putc('-'), x = -x;if (!x) putc('0');while (x) que[++ num] = x % 10 + 48, x /= 10;while (num) putc(que[num --]);}struct Flusher_{~Flusher_(){flush();}} io_Flusher_; } using FastIO :: read; using FastIO :: putc; using FastIO :: reads; using FastIO :: print;ll ans = 0; vector<int> e[MAXN]; int dep[MAXN], Log[MAXN], a[MAXN], fa[MAXN][20], id, n; void dfs(int x, int father) {dep[x] = dep[father] + 1, fa[x][0] = father;for (int i = 1; i <= Log[dep[x]] ; ++ i) fa[x][i] = fa[fa[x][i - 1]][i - 1];for (auto v : e[x]) {if (v == father) continue;dfs(v, x);}if (father) {ll mn = 1ll * (Log[dep[x]] + 1) * a[id] + a[id] + a[x];for (int i = 0; i <= Log[dep[x]] ; ++ i) upmin(mn, 1ll * min(a[x], a[fa[x][i]]) * i + a[x] + a[fa[x][i]]);ans += mn;} } signed main() { #ifndef ONLINE_JUDGEfreopen("a.in", "r", stdin); #endifread(n);Log[1] = 0, dep[0] = -1, id = 1;for (int i = 2; i <= n ; ++ i) Log[i] = Log[i >> 1] + 1;for (int i = 1; i <= n ; ++ i) {read(a[i]);if (a[i] < a[id]) id = i;}for (int i = 1, u, v; i < n ; ++ i) read(u), read(v), e[u].PB(v), e[v].PB(u);dfs(id, 0);print(ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF1088F. Ehab and a weird weight formula(倍增)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。