Xor Tree

#include <iostream>
#include <vector>

using namespace std;

const int NMAX = 2e5;

int N;
vector <int> g[NMAX + 2];
long long cst[NMAX + 2];

const long long INF = 1e18;
long long dp[NMAX + 2][2];

void dfs(int node, int dad)
{

    if(node != 1 && g[node].size() == 1)
    {
        dp[node][0] = cst[node];
        dp[node][1] = 0;
        return ;
    }

    dp[node][0] = dp[node][1] = -INF;

    for(auto it : g[node])
        if(it != dad)
        {
            dfs(it, node);

            if(dp[node][0] == -INF)
            {
                dp[node][0] = dp[it][0];
                dp[node][1] = dp[it][1];
                continue;
            }

            long long dp0 = dp[node][0], dp1 = dp[node][1];

            dp[node][0] = max(dp0 + dp[it][0], dp1 + dp[it][1]);
            dp[node][1] = max(dp1 + dp[it][0], dp0 + dp[it][1]);
        }

    dp[node][0] += cst[node];
}

int main()
{
    cin >> N;

    for(int i = 1; i < N; i++)
    {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    for(int i = 1; i <= N; i++)
        cin >> cst[i];

    dfs(1, -1);

    cout << max(dp[1][0], dp[1][1]) << '\n';

    return 0;
}