题目描述
树Dp
int qr(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
vector<int > v[100005], vis(100010, 0);
vector<int > l(100010, 0), r(100010, 0);
int dp[100010][2];
int ans = 0;
void dfs(int x) {
vis[x] = 1;
for(auto it : v[x]) {
if(vis[it]) continue;
if(vis[it] == 0) dfs(it);
dp[x][0] += max(dp[it][0] + abs(l[x] - l[it]), dp[it][1] + abs(l[x] - r[it]));
dp[x][1] += max(dp[it][0] + abs(r[x] - l[it]), dp[it][1] + abs(r[x] - r[it]));
}
}
void work(){
int n = qr();
for(int i = 1;i <= n;i++) l[i] = qr(), r[i] = qr();
for(int i = 1;i <= n;i++) v[i].clear(), vis[i] = 0, dp[i][0] = 0, dp[i][1] = 0;
for(int i = 1;i <= n - 1;i++) {
int st = qr(), end = qr();
v[st].pb(end);
v[end].pb(st);
}
dfs(1);
cout << max(dp[1][0] , dp[1][1]) << endl;
}
int32_t main(int32_t argc,char **argv){
int _ = 1;
_ = qr();
while(_--) work();
return 0;
}
样例
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla