wys的个人博客

你有很多事放不下？做人要潇洒一点~

0%

A. Parsa's Humongous Tree

Posted on Edited on In

Codeforces Round #722 (Div. 1)

我们设 $dp[i][0]$ 为第$i$个节点选左端点时，该端点及其子树的边权的最大值。

​ $dp[i][1]$ 为第$i$个节点选右端点时，该端点及其子树的边权的最大值。

我们设父节点为 $x$ ,子节点为 $it$ ,节点$i$的左节点为$nd[i][0]$,右节点为$nd[i][1]$，则dp转移表达式为

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i)
#define pb push_back
#define int long long
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>PII;
const double eps = 1e-8;
const int maxn = 200000 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
//unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
//mt19937 rand_num(seed);

int node[maxn][3];
vector<int> vec[maxn];
int dp[maxn][3];

int dfs(int x,int flag,int fa){
    if(dp[x][flag]!=-1) return dp[x][flag];
    int& res = dp[x][flag];
    res = 0;
    for(auto it:vec[x]){
        if(it != fa){
            res += max(dfs(it,0,x)+abs(node[it][0]-node[x][flag]),dfs(it,1,x)+abs(node[it][1]-node[x][flag]));
        }
    }
    return res;
}

signed main(){
    
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    //std::ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        for(int i=1;i<=n;i++) {
            dp[i][1] = -1;dp[i][0]=-1;  
            vec[i].clear();
        }
        for(int i=1;i<=n;i++){
            scanf("%lld%lld",&node[i][0],&node[i][1]);
        }
        int u,v;
        for(int i=1;i<n;i++){
            scanf("%lld%lld",&u,&v);
            vec[u].push_back(v);
            vec[v].push_back(u);
        }
        printf("%lld\n",max(dfs(1,0,-1),dfs(1,1,-1)));
    }

    return 0;
}