題目鏈接

https://atcoder.jp/contests/agc029/tasks/agc029_e

題解

寫了一半發現假了然后強行亂改一通改對了……
我們用“\(u\)子樹內小于\(x\)的連通塊”來表示\(u\)子樹內到\(u\)路徑上的點都小于\(x\)的點（包括\(u\)）的集合，集合的大小用\(C(u,x)\)表示。
考慮這個游走的過程，設點\(u\)到根的路徑上分別是\(u=u_1,u_2,u_3,...,u_{k-1},u_k=1\), 則對于\(i\)來說干的事情是“把\(u_i\)子樹內小于\(u_{i+1}\)的連通塊都走一遍”。那么對于一個\(i\)來說若存在\(j>i\)且\(u_{j+1}>u_{i+1}\), 那么后者的作用會包含前者，前者無用。也就是說我們要考慮根到每個點路徑上的前綴最大值（就是每個點到根路徑上的后綴最大值）。
考慮遞推，從父親遞推到兒子。設\(mx[u]\)表示\(u\)到根路徑上的最大值，\(v\)是\(u\)的兒子，經過簡單推導可得如下遞推式:

ans[v] = ans[u]; if(u>mx[fa[u]]) {ans[v] += C(v,mx[u])-C(v,mx[fa[u]]);} //u是前綴最大值點 if(v>mx[u]) {ans[v] += 所有v的兒子v'的C(v',mx[u])之和+1;} //v是前綴最大值點

第三行是因為v>mx[u]所以v的子樹不被包括在上一次的最大值點計算的貢獻中，需要重新計算。
（我知道這樣講很不清楚……可是抱歉博主實在是不知道如何用文字把這個推導過程寫清楚，并且這個實際上也挺簡單的仔細推一推應該能推出來）
現在考慮如何對每個前綴最大值的\(u\)的每個兒子\(v\)求出\(C(v,mx[u])\)和\(C(v,mx[fa[u]])\). 看起來需要數據結構，但是我們發現所有這些值的總和是\(O(n)\)級別的，所以暴力枚舉就可以了。
時間復雜度\(O(n)\).

代碼

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define riterator reverse_iterator using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int N = 2e5; struct Edge {int nxt,v; } e[(N<<1)+3]; int fe[N+3]; int fa[N+3]; int mx[N+3]; int f[N+3],g[N+3],h[N+3]; int ans[N+3]; int n,en;void addedge(int u,int v) {en++; e[en].v = v;e[en].nxt = fe[u]; fe[u] = en; }int dfs2(int u,int x) {if(u>x) return 0;int ret = 1;for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v; if(v==fa[u]) continue;ret += dfs2(v,x);}return ret; }void dfs1(int u) {for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v; if(v==fa[u]) continue;fa[v] = u;mx[v] = max(mx[u],v);dfs1(v);}if(u>mx[fa[u]]){h[u] = 1;for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v; if(v==fa[u]) continue;f[v] = dfs2(v,u);g[v] = dfs2(v,mx[fa[u]]); h[u] += g[v];}} }void dfs3(int u) {for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v; if(v==fa[u]) continue;ans[v] = ans[u]; if(u>mx[fa[u]]) {ans[v] += f[v]-g[v];} if(mx[v]>mx[u]) {ans[v] += h[v];}dfs3(v);} }int main() {scanf("%d",&n);for(int i=1; i<n; i++){int u,v; scanf("%d%d",&u,&v);addedge(u,v); addedge(v,u);}mx[1] = 1; f[1] = 1; dfs1(1); // printf("f: "); for(int i=1; i<=n; i++) printf("%d ",f[i]); puts(""); // printf("g: "); for(int i=1; i<=n; i++) printf("%d ",g[i]); puts(""); // printf("h: "); for(int i=1; i<=n; i++) printf("%d ",h[i]); puts("");dfs3(1);for(int i=2; i<=n; i++) printf("%d ",ans[i]); puts("");return 0; }

總結

以上是生活随笔為你收集整理的AtCoder AGC029E Wandering TKHS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。