題目鏈接：點擊查看

題目大意：給出一棵初始時只有一個點的樹，每個點都有兩個值：$a_i,c_i$，分別代表黃金的個數(shù)和單價。需要執(zhí)行 $m$ 次操作，每次操作分為兩種類型：

$1p_i{a}_i{c}_i$添加一個新點 $i$，$p_i$ 為其父節(jié)點，$a_i,c_i$ 如上一段所述，保證 $c_i>c_{p_i}$

$2vw$：需要從點 $v$ 到根節(jié)點的這條路徑上采集 $w$ 個單位的黃金，問如何采集才能使得總花費最少

注意對于每次操作 $2$ 是會疊加的，且強制在線

題目分析：如果觀察到 $c_i>c_{p_i}$ 這個條件的話，不難看出這是個很簡單的數(shù)據(jù)結(jié)構(gòu)+貪心了，因為每次挑選的點，都是靠近根節(jié)點且連續(xù)的一系列非空節(jié)點

所以問題轉(zhuǎn)換為了：

插入一個新點

查找某個點的深度最小的非空祖先

刪除掉某個節(jié)點

不難想到樹上倍增，因為之前也做過一個強制在線增加新點的題目:CodeForces - 932D

相應(yīng)的處理方法如下：

對于新點 $O(logn)$ 預(yù)處理倍增數(shù)組

查找 $a_x$ 非空的祖先

令 $a_x=0$

時間復(fù)雜度的話，每次遍歷到一個祖先節(jié)點，要么被刪除，要么就停止，而查找祖先節(jié)點的復(fù)雜度是 $O(lgon)$ 的，所以時間復(fù)雜度是 $O(nlogn)$

代碼：

// Problem: E. Gold Transfer // Contest: Codeforces - Educational Codeforces Round 110 (Rated for Div. 2) // URL: https://codeforces.com/contest/1535/problem/E // Memory Limit: 256 MB // Time Limit: 4500 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #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> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; int a[N],c[N],dp[N][25]; int get_fa(int u) {for(int i=20;i>=0;i--) {if(a[dp[u][i]]) {u=dp[u][i];}}return u; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d%d%d",&n,&a[0],&c[0]);for(int i=1;i<=n;i++) {int op;scanf("%d",&op);if(op==1) {scanf("%d%d%d",&dp[i][0],a+i,c+i);for(int j=1;j<=20;j++) {dp[i][j]=dp[dp[i][j-1]][j-1];}} else if(op==2) {int v,w;LL ans1=0,ans2=0;scanf("%d%d",&v,&w);while(a[v]&&w) {int u=get_fa(v);int mmin=min(a[u],w);w-=mmin;a[u]-=mmin;ans1+=mmin;ans2+=1LL*mmin*c[u];}printf("%lld %lld\n",ans1,ans2);fflush(stdout);}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1535E Gold Transfer(树上倍增+交互)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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