題目鏈接：點擊查看

題目大意：給出一棵有根樹，每個節(jié)點都有權值，滿足所有葉子結點到根節(jié)點的距離相同，初始時在根節(jié)點有兩個硬幣，分別是紅色和藍色，每次可以執(zhí)行如下操作：

將紅色硬幣移動到任意一個子節(jié)點

將藍色硬幣移動到下一層的任意一個節(jié)點

（可選）交換紅色硬幣和藍色硬幣

本次操作的貢獻是紅色硬幣和藍色硬幣點權之差的絕對值

問如何移動可以使得貢獻之和最大

題目分析：不算難的一道樹形 $dp$，因為藍色硬幣可以是下一層的任意節(jié)點，所以只需要關注紅色硬幣移動的路線就可以了，不妨設 $d{p}_i$ 為紅色硬幣在點 $i$ 時移動到葉子結點的最大貢獻和，選擇自底向上轉移，這樣就將原樹中的節(jié)點劃分成不同層次之間的轉移了。

分成兩種情況討論：

不交換硬幣：那么 $d{p}_u=d{p}_v+|a_v?a_m|$，因為不交換的話，紅色硬幣下一步一定到達點 $u$ 的子節(jié)點 $v$，而 $m$ 是藍色節(jié)點的位置，我們可以選擇同層中任意節(jié)點來充當

交換硬幣：那么 $d{p}_u=d{p}_m+|a_v?a_m|$，類比于上面的情況，藍色節(jié)點一定是 $v$ 了，而同層的任意一個節(jié)點可以充當紅色節(jié)點

乍一看轉移的復雜度不是很可觀，但是這些東西是可以預處理的，第一種情況我們只需要維護一下 $a_m$ 的最小值和最大值輔助轉移即可，第二種情況需要預處理一下 $d{p}_m?a_m$ 和 $d{p}_m+a_m$ 的最大值輔助轉移就好啦

代碼：

// Problem: E. Move and Swap // Contest: Codeforces - Codeforces Round #701 (Div. 2) // URL: https://codeforces.com/contest/1485/problem/E // Memory Limit: 256 MB // Time Limit: 2000 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 LL inf=0x3f3f3f3f3f3f3f3f; const int N=1e6+100; int fa[N],max_deep; LL dp[N],a[N]; vector<int>node[N],d[N]; void dfs(int u,int f,int dep) {max_deep=max(max_deep,dep);fa[u]=f;d[dep].push_back(u);for(auto v:node[u]) {dfs(v,u,dep+1);} } void init(int n) {for(int i=1;i<=n;i++) {node[i].clear();d[i].clear();}memset(dp,0,sizeof(LL)*(n+5));max_deep=0; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--) {int n;read(n);init(n);for(int i=2;i<=n;i++) {int fa;read(fa);node[fa].push_back(i);}for(int i=2;i<=n;i++) {read(a[i]);}dfs(1,-1,1);for(int i=max_deep;i>1;i--) {//不交換LL mmax=-inf,mmin=inf;for(auto u:d[i]) {mmax=max(mmax,a[u]);mmin=min(mmin,a[u]);}for(auto u:d[i]) {dp[fa[u]]=max(dp[fa[u]],dp[u]+max(llabs(a[u]-mmax),llabs(a[u]-mmin)));}//交換LL mmax1=-inf,mmax2=-inf;for(auto u:d[i]) {mmax1=max(mmax1,dp[u]+a[u]);mmax2=max(mmax2,dp[u]-a[u]);}for(auto u:d[i]) {dp[fa[u]]=max(dp[fa[u]],mmax1-a[u]);dp[fa[u]]=max(dp[fa[u]],mmax2+a[u]);}}cout<<dp[1]<<endl;}return 0; } 超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的CodeForces - 1485E Move and Swap(树形dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

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