題目鏈接：點擊查看

題目大意：給出一棵樹，初始時只有一個節點1，權值為0，后續有 n 個操作，每次操作分為兩種情況：

1 u val：向樹中插入一個新的節點，其父節點為 u ，權值為 val

2 u val：詢問以節點 u 為起點的最長不下降子序列的長度，這里規定的最長不下降子序列需要滿足以下幾個條件：

以 u 為起點，每次的路線必須都是當前節點的父節點

序列中的權值和小于等于 val

題目分析：因為操作二需要每次按照要求往祖先節點上跳，我們不妨設計一下倍增來處理所需要解決的問題

dp[ u ][ i ]：代表節點 u 向上經過 2^i 個權值大于等于 w[u] 的結點后的位置

sum[ u ][ i ]：代表節點 u 向上經過 2^i 個權值大于等于 w[u] 后的權值和(只統計這 2^i 個數)

有了這兩個數組的定義后，那么我們在插入時，可以logn維護一下這兩個數組，在查詢時，也可以logn獲得答案，有很多細節，具體實現看代碼吧：

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<cmath> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const LL inf=0x3f3f3f3f3f3f3f3f;const int N=4e5+100;LL last,dp[N][25],sum[N][25],w[N],cur;void add(LL u,LL val) {u^=last;val^=last;w[++cur]=val;if(w[cur]<=w[u])//處理dp[u][0]dp[cur][0]=u;else{for(int i=20;i>=0;i--)if(w[cur]>w[dp[u][i]])u=dp[u][i];dp[cur][0]=dp[u][0];}if(dp[cur][0]==0)//處理sum[u][0]sum[cur][0]=inf;elsesum[cur][0]=w[dp[cur][0]];for(int i=1;i<=20;i++)//維護dp數組和sum數組{dp[cur][i]=dp[dp[cur][i-1]][i-1];if(dp[cur][i]==0)sum[cur][i]=inf;elsesum[cur][i]=sum[cur][i-1]+sum[dp[cur][i-1]][i-1];} }LL query(LL u,LL val) {u^=last;val^=last;if(w[u]>val)return 0;LL ans=1;val-=w[u];for(int i=20;i>=0;i--)//統計答案{if(val>=sum[u][i]){val-=sum[u][i];ans+=(1<<i);u=dp[u][i];}}return ans; }void init()//初始化sum數組到所有不可能到達的位置為無窮大 {w[0]=inf;w[1]=0;last=0;cur=1;for(int i=0;i<=20;i++)sum[1][i]=inf; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);init();int n;scanf("%d",&n);while(n--){LL op,p,q;scanf("%lld%lld%lld",&op,&p,&q);if(op==1)add(p,q);elseprintf("%lld\n",last=query(p,q));}return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 932D Tree(树上倍增，好题)的全部內容，希望文章能夠幫你解決所遇到的問題。

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