題目鏈接

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

題解

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

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

第三行是因?yàn)関>mx[u]所以v的子樹不被包括在上一次的最大值點(diǎn)計(jì)算的貢獻(xiàn)中，需要重新計(jì)算。
（我知道這樣講很不清楚……可是抱歉博主實(shí)在是不知道如何用文字把這個(gè)推導(dǎo)過程寫清楚，并且這個(gè)實(shí)際上也挺簡(jiǎn)單的仔細(xì)推一推應(yīng)該能推出來）
現(xiàn)在考慮如何對(duì)每個(gè)前綴最大值的\(u\)的每個(gè)兒子\(v\)求出\(C(v,mx[u])\)和\(C(v,mx[fa[u]])\). 看起來需要數(shù)據(jù)結(jié)構(gòu)，但是我們發(fā)現(xiàn)所有這些值的總和是\(O(n)\)級(jí)別的，所以暴力枚舉就可以了。
時(shí)間復(fù)雜度\(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; }

總結(jié)

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

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