Codeforces1529C（树形dp）

题目链接

令dp[u][0/1] 表示u节点选取L或者R能收获的最大贡献。 考虑树形dp&＃xff0c;最终把答案汇聚在根上。因此转移方程为
dp[u][0]&＃43;&＃61;max(dp[v][0]&＃43;abs(a[u][0]-a[v][0]),dp[v][1]&＃43;abs(a[u][0]-a[v][1]));
dp[u][1]&＃43;&＃61;max(dp[v][0]&＃43;abs(a[u][1]-a[v][0]),dp[v][1]&＃43;abs(a[u][1]-a[v][1]));


ll dp[100100][3];
vector<ll>G[100100];
ll a[100100][3];void dfs(ll u,ll f)
{dp[u][0]&＃61;dp[u][1]&＃61;0;for(int i&＃61;0; i<G[u].size(); i&＃43;&＃43;){ll v&＃61;G[u][i];if(v&＃61;&＃61;f)continue;dfs(v,u);dp[u][0]&＃43;&＃61;max(dp[v][0]&＃43;abs(a[u][0]-a[v][0]),dp[v][1]&＃43;abs(a[u][0]-a[v][1]));dp[u][1]&＃43;&＃61;max(dp[v][0]&＃43;abs(a[u][1]-a[v][0]),dp[v][1]&＃43;abs(a[u][1]-a[v][1]));}return ;
}
signed main()
{ll t;read(t);while(t--){ll n;read(n);for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;){read(a[i][0]);read(a[i][1]);}memset(dp,0,sizeof(dp));for(int i&＃61;1; i<n; i&＃43;&＃43;){ll u,v;read(u);read(v);G[u].push_back(v);G[v].push_back(u);}dfs(1,1);printf("%lld\n",max(dp[1][1],dp[1][0]));for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;){G[i].clear();}}}