題意

給你一顆有 \(n\) 個(gè)點(diǎn)并且以 \(1\) 為根的樹(shù)。共有 \(q\) 次詢問(wèn)，每次詢問(wèn)兩個(gè)參數(shù) \(p, k\) 。詢問(wèn)有多少對(duì)點(diǎn) \((p, a, b)\) 滿足 \(p,a,b\) 為三個(gè)不同的點(diǎn)，\(p, a\) 都為 \(b\) 的祖先，且 \(p\) 到 \(a\) 的距離不能超過(guò) \(k\) 。

\(n\le 300000 , q\le 300000\) 不要求強(qiáng)制在線。

題解

令 \(dep[u]\) 為點(diǎn) \(u\) 的深度，\(sz[u]\) 為 \(u\) 的子樹(shù)大小（除去 \(u\) 本身）

首先我們考慮兩種情況：

\(a\) 為 \(p\) 的祖先，那么這部分貢獻(xiàn)很好計(jì)算，就是 \(\min\{dep[p] - 1,k\} \times sz[u]\) 。

\(a\) 在 \(p\) 的子樹(shù)內(nèi)，那么這部分貢獻(xiàn)就是 \(\displaystyle \sum_{dis(p,a) \le k} sz[a]\) 。

我們現(xiàn)在只要考慮第二部分貢獻(xiàn)怎么求。

不難發(fā)現(xiàn)，這些點(diǎn)的深度就是 \([dep[p], dep[p]+k]\) 這個(gè)范圍內(nèi)的。

那么我們可以對(duì)于每個(gè)點(diǎn)用個(gè) 主席樹(shù) 來(lái)存儲(chǔ)這些信息，可以在線回答詢問(wèn)。

那么離線的話，可以考慮用 線段樹(shù)合并 維護(hù)它每個(gè)子樹(shù)的信息。

具體來(lái)說(shuō)，這些都是對(duì)于每個(gè) \(dep\) 維護(hù)它的 \(sz\) 的和，然后查區(qū)間和就行了。

然而這些時(shí)空復(fù)雜度都是 \(O(n \log n)\) ，其實(shí)還有更好的做法。

為什么我發(fā)現(xiàn)了呢qwq？

因?yàn)?fatesky 做這道題線段樹(shù)合并做法的時(shí)候，Wearry 說(shuō)可以 長(zhǎng)鏈剖分 那就是 \(O(n)\) 的啦。

我們令 \(\displaystyle maxdep[u]=\max_{v \in child[u]} \{dep[v\}\) 也就是它子樹(shù)中的最大深度。

具體來(lái)說(shuō)，長(zhǎng)鏈剖分就是把每個(gè)點(diǎn)兒子中 \(maxdep\) 最大的那個(gè)當(dāng)做重兒子。重兒子與父親連的邊叫做重邊。一連串重邊不間斷連到一起就叫做重鏈。

然后我們就有一條性質(zhì)。

性質(zhì)1 : 重鏈長(zhǎng)度之和是 \(O(n)\) 的。

這個(gè)很顯然啦，因?yàn)榭偣仓挥?\(O(n)\) 級(jí)別的邊。

有了這個(gè)我們就可以解決一系列 關(guān)于深度的動(dòng)態(tài)規(guī)劃 問(wèn)題了，對(duì)于這列問(wèn)題常常都可以做到 \(O(n)\) 的復(fù)雜度。

具體操作就是，每次暴力繼承重兒子的 \(dp\) 狀態(tài)，然后輕兒子暴力合并上去。

不難發(fā)現(xiàn)這個(gè)復(fù)雜度是 \(O(\sum\) 重鏈長(zhǎng) \()\) \(= O(n)\) 的。

繼承的時(shí)候常常需要移位，并且把當(dāng)前節(jié)點(diǎn)貢獻(xiàn)算入，并且這個(gè) \(dp\) 需要?jiǎng)討B(tài)空間才能實(shí)現(xiàn)。

對(duì)于這道題我們考慮維護(hù)一個(gè)后綴和，也就是對(duì)于 \(u\) 子樹(shù)中的 \(v\) ，\(dep[v] \ge k\) 的所有 \(sz[v]\) 的和。

不難發(fā)現(xiàn)后綴和是很好合并的，這個(gè)的復(fù)雜度只需要 \(O(\min maxdep[v])\) 。

每次添加一個(gè)點(diǎn) \(sz[u]\) 對(duì)于 \(dep[u]\) 的貢獻(xiàn)只會(huì)對(duì)一個(gè)點(diǎn)的貢獻(xiàn)產(chǎn)生影響，這個(gè)復(fù)雜度是 \(O(1)\) 的。

代碼實(shí)現(xiàn)的話，就可以用一個(gè) std :: vector ，按深度從大到小 （ \(maxdep[u] \to dep[u]\) ）存儲(chǔ)每個(gè)點(diǎn)的信息，因?yàn)檫@樣最方便繼承重兒子狀態(tài)（每次加入狀態(tài)只在整個(gè) vector 末端添加一個(gè)元素）

其實(shí)可以動(dòng)態(tài)開(kāi)內(nèi)存，順著做，但我似乎學(xué)不來(lái)

常數(shù)似乎有點(diǎn)大，沒(méi)比 \(O(n \log n)\) 快多少，vector 用多了... Wearry 到是優(yōu)化了點(diǎn)常數(shù)到了 \(4000+ ms\) 。

話說(shuō)這個(gè)很像原來(lái) DOFY 講過(guò)的那道 Dsu on Tree ？

代碼

#include <bits/stdc++.h>#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i) #define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i) #define Set(a, v) memset(a, v, sizeof(a)) #define Cpy(a, b) memcpy(a, b, sizeof(a)) #define debug(x) cout << #x << ": " << x << endl #define DEBUG(...) fprintf(stderr, __VA_ARGS__)using namespace std;typedef long long ll;inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;} inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}inline int read() {int x = 0, fh = 1; char ch = getchar();for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);return x * fh; }void File() { #ifdef zjp_shadowfreopen ("3653.in", "r", stdin);freopen ("3653.out", "w", stdout); #endif }const int N = 3e5 + 1e3;struct Ask { int k, id; } ; vector<Ask> V[N];vector<int> G[N]; int sz[N], maxdep[N], dep[N], sonmaxdep[N], son[N], rt[N];vector<ll> sum[N]; int n, q; ll ans[N], Size = 0;void Dfs_Init(int u, int fa = 0) {maxdep[u] = dep[u] = dep[fa] + 1;For (i, 0, G[u].size() - 1) {register int v = G[u][i];if (v ^ fa) Dfs_Init(v, u), chkmax(maxdep[u], maxdep[v]);}}void Dfs(int u, int fa = 0) {For (i, 0, G[u].size() - 1) {int v = G[u][i];if (v == fa) continue ;Dfs(v, u); sz[u] += sz[v];if (maxdep[v] > maxdep[son[u]]) son[u] = v;}rt[u] = rt[son[u]]; if (!rt[u]) rt[u] = ++ Size;int len = (int)sum[rt[u]].size();ll Last = len ? sum[rt[u]][len - 1] : 0;sum[rt[u]].push_back(Last);if (son[u]) {For (i, 0, G[u].size() - 1) {int v = G[u][i]; if (v == fa || v == son[u]) continue ;For (j, 0, sum[rt[v]].size() - 1) {int nowdep = (maxdep[son[u]] - maxdep[v]) + j;sum[rt[u]][nowdep] += sum[rt[v]][j];}sum[rt[u]][len] += sum[rt[v]][sum[rt[v]].size() - 1];}}For (i, 0, V[u].size() - 1) {Ask now = V[u][i];ans[now.id] = sum[rt[u]][len];if (len > now.k) ans[now.id] -= sum[rt[u]][len - now.k - 1];ans[now.id] += 1ll * min(dep[u] - 1, now.k) * sz[u];}sum[rt[u]][len] += sz[u]; ++ sz[u];}int main () {File();n = read(); q = read();For (i, 1, n - 1) {int u = read(), v = read();G[u].push_back(v);G[v].push_back(u);}For (i, 1, q) {int p = read(), k = read();V[p].push_back((Ask) {k, i});}Dfs_Init(1); Dfs(1);For (i, 1, q)printf ("%lld\n", ans[i]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/zjp-shadow/p/9262234.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 3653: 谈笑风生（离线, 长链剖分, 后缀和）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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