C. Parsa's Humongous Tree
显然可以证明我们的每一个节点肯定是会取到边界值才是最优解
比如 我们当前其他节点确定
我们中间节点v不确定 我们让av从lv开始
av++ 如果旁边节点的数大于av的较多 我们贡献减少 如果旁边节点的数大于av的较少我们的贡献增加
显然这是一个单峰函数
我们显然只能在旁边两个点取到极值
然后我们可以想到的就是直接大小大小这样填
显然这样是不合理的 所以我们dp
我们显然对于lr需要一个状态 然后就是类似树形dp
dp[i][0/1]表示i子树的ai选li还是ri的max
转移就很简单了 直接暴力A22
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 1e9+7;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int n,dp[N][2],l[N],r[N];
vector<int>g[N];
void dfs(int u,int fa){
for(auto v:g[u]){
if(v==fa)continue;
dfs(v,u);
dp[u][0]+=max(dp[v][0]+abs(l[u]-l[v]),dp[v][1]+abs(l[u]-r[v]));
dp[u][1]+=max(dp[v][0]+abs(r[u]-l[v]),dp[v][1]+abs(r[u]-r[v]));
}
}
void solve() {
cin>>n;
for(int i=1;i<=n;i++)g[i].clear(),dp[i][0]=dp[i][1]=0;
for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
cout<<max(dp[1][0],dp[1][1])<<endl;
}
signed main(){
fast
int t;t=1;cin>>t;
while(t--) {
solve();
}
return ~~(0^_^0);
}
标签:const,int,Codeforces,节点,abs,722,av,Round,dp
From: https://www.cnblogs.com/ycllz/p/16802347.html