1475E - Advertising Agency（dfs、dp）

刺骨的言语ヽ痛彻心扉 2021-07-16 14:38 315阅读 0赞

[题目][Link 1]

思路：对于一个结点有四种情况00 11 10 01，其中00 11我们不需要重新交换。然后因为每个子树都可用其父亲及往上的结点的值交换。故我们从上到下更新每一个结点的交换值，其值为min(自己，父亲)。然后从1开始dfs，先深入到最底下结点,让下面的结点先进行交换（因为越往下的结点花费越少），还剩下的没交换的给其父节点，一层层往上，如果最终都还剩下没交换好的，则不可能全交换。

Code:

#include<iostream>
    #include<vector>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 2e5 + 5;
    ll v[Max], a[Max], b[Max];
    vector<int> g[Max];
    ll ans = 0;
    
    pair<int, int> dfs(int u, int par)
    { 
    	pair<int, int> p = make_pair(0, 0);
    	v[u] = min(v[u], v[par]);
    	if (a[u] != b[u])
    	{ 
    		if (a[u])p.first++;
    		else p.second++;
    	}
    	for (auto i : g[u])
    	{ 
    		if (i == par)continue;
    		pair<int, int> g = dfs(i, u);
    		p.first += g.first;
    		p.second += g.second;
    	}
    	ll mi = min(p.second, p.first);
    	ans += v[u] * mi * 2;
    	p.first -= mi;p.second -= mi;
    	return p;
    }
    
    int main()
    { 
    	FAST;
    	int n;cin >> n;
    	for (int i = 1;i <= n;i++)cin >> v[i] >> a[i] >> b[i];
    	for (int i = 1;i <= n - 1;i++)
    	{ 
    		int o, p;cin >> o >> p;
    		g[o].push_back(p);
    		g[p].push_back(o);
    	}
    	pair<int, int> res = dfs(1, 1);
    	if (res.first || res.second)cout << -1 << endl;
    	else cout << ans << endl;
    }

[Link 1]: https://codeforc.es/problemset/problem/1363/E