題目鏈接：點擊查看

題目大意：給出一棵 n 個節(jié)點且以點 1 為根節(jié)點的的樹，現(xiàn)在給出一個 k ，需要在樹上選擇 k 個關(guān)鍵點，使得 n 個點到達根節(jié)點的路徑上，出現(xiàn)的最近的關(guān)鍵點的距離的最大值最小，現(xiàn)在需要輸出 k 分別為 1 ~ n 時的答案之和

題目分析：首先理解題意，這個題目中有且僅由一個思維點需要轉(zhuǎn)換過來，那就是直接計算 k 值下的答案是很難計算的，但是我們可以在某個答案下，貪心去計算 k 的值

怎么理解上面這段話呢？對于某個答案 x 來說，因為 x 是題目中所有距離最大值的最小值，換句話說，任何一個點到達根節(jié)點的路徑上，相離最近的那個關(guān)鍵點的距離一定小于等于 x 的，這樣的話我們可以貪心去模擬，假設(shè) x 已經(jīng)確定了，可以先找到當前深度最深的那個節(jié)點，顯然如果想要讓這個節(jié)點距離最近的關(guān)鍵點的距離小于等于 x 的話，那么令其向上的第 x 個祖先設(shè)置為關(guān)鍵點就好了，當剛才的那個祖先被設(shè)置為關(guān)鍵點后，其子樹上的所有點也就都滿足條件了（因為最深的那個點都滿足條件了，那么其余的點顯然也是滿足條件的），依次類推，貪心去模擬就能計算出 k 的值了

現(xiàn)在我們需要選擇合適的數(shù)據(jù)結(jié)構(gòu)去實現(xiàn)上述操作，對于上段所述的功能一一對應(yīng)一下，子樹對應(yīng)著dfs序，有了dfs序就可以建立線段樹，這樣每次找深度最深的結(jié)點就可以用線段樹維護dfs序上深度的最大值，找向上第 x 個祖先，對應(yīng)著樹上倍增，然后就是枚舉答案了，顯然答案的可行范圍是 0 ~ n - 1 （當所有點都是關(guān)鍵點時，答案為 0 ，當只有根節(jié)點是關(guān)鍵點，且整棵樹退化為鏈時，那么答案就是 n - 1 ），對于每次枚舉的答案為 i ，貪心需要模擬的次數(shù)就為 n / i ，整體的時間復雜度就是?（調(diào)和級數(shù)），再加上線段樹更新需要的一層log，總的時間復雜度為 nlognlogn

注意一下，因為可能會出現(xiàn)不同的答案對應(yīng)著相同的 k 值，所以我們可以倒著枚舉答案，最后再正著維護一下答案的最小值就好了，因為根據(jù)貪心的策略，ans[ i ] 代表的就是當 k = i 時的答案，顯然在 ans[ i ] 的策略上再增加關(guān)鍵點的話，ans[ i + 1 ] 一定是小于等于 ans[ i?] 的，所以從前往后維護最小值是可行的

最后就是對于線段樹的更新，對于每個樣例我們只需要 build 一次線段樹即可，對于每個答案在更新線段樹的時候，記錄一下更新的位置，計算完答案后再原路恢復就好了，如果對于每個答案都重新 build 的話，時間復雜度就會退化成 n * n * logn * logn

代碼：
?

#pragma comment(linker,"/STACK:102400000,102400000") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;int dp[N][25],ans[N],L[N],R[N],id[N],deep[N],cnt,limit,n;vector<int>node[N];void dfs(int u,int dep) {deep[u]=dep;L[u]=++cnt;id[cnt]=u;for(int i=1;i<=limit;i++)dp[u][i]=dp[dp[u][i-1]][i-1];for(auto v:node[u])dfs(v,dep+1);R[u]=cnt; }struct Node {int id,deep;bool operator<(const Node& t)const{if(deep!=t.deep)return deep<t.deep;return id<t.id;} }tree[N<<2],temp[N<<2];int tot=0;void build(int k,int l,int r) {if(l==r){tree[k].deep=deep[id[l]];tree[k].id=id[l];temp[k]=tree[k];return;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);temp[k]=tree[k]=max(tree[k<<1],tree[k<<1|1]); }void update(int k,int l,int r,int L,int R,int op)//l,r:目標區(qū)間,L,R:當前區(qū)間 {if(R<l||L>r)return;if(L>=l&&R<=r){if(op==1)tree[k].deep=-1;elsetree[k].deep=temp[k].deep;return;}int mid=L+R>>1;update(k<<1,l,r,L,mid,op);update(k<<1|1,l,r,mid+1,R,op);tree[k]=max(tree[k<<1],tree[k<<1|1]); }int get_fa(int u,int x) {for(int i=0;i<=limit;i++)if(x&(1<<i))u=dp[u][i];return max(u,1); }int cal(int x) {int num=0;vector<int>cls;//恢復操作用 while(tree[1].deep!=-1){num++;int pos=get_fa(tree[1].id,x);cls.push_back(pos);update(1,L[pos],R[pos],1,n,1);}for(auto v:cls)update(1,L[v],R[v],1,n,-1);return num; }void init(int n) {limit=log2(n)+1;cnt=0;for(int i=0;i<=n;i++){ans[i]=inf;node[i].clear();} }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);while(scanf("%d",&n)!=EOF){init(n);for(int i=2;i<=n;i++){scanf("%d",&dp[i][0]);node[dp[i][0]].push_back(i);}dfs(1,0);build(1,1,n);for(int i=n;i>=0;i--){int q=cal(i);ans[q]=i;}for(int i=1;i<=n;i++)ans[i]=min(ans[i],ans[i-1]);LL ans=0;for(int i=1;i<=n;i++)ans+=::ans[i];printf("%lld\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的牛客多校4 - Ancient Distance(树上倍增+dfs序+线段树)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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