#22900 나의 라임 오렌지나무

https://www.acmicpc.net/problem/22900

 

문제요약: 트리가 주어지고 간선에 가중치가 주어진다. 
간선은 가중치가 존재할 때만 이용할 수 있다.

한번 움직일때마다 가중치를 원하는 만큼 뺀다.
움직일 수 없게 되는 사람이 지게 된다.
모든 시작위치에 대해서 선/후 공 중 누가 이기는지 구해라.

우선 가중치를 없애자.

어차피 모든 간선은 1번만 이용하는 걸로 생각해도 된다. 
(왜 그런지는 생각해보자.)

 

그럼 다음과 같은 tree dp형태로 바뀐다.

 

승리를 1, 패배를 0으로 칠한다면,

시작정점과 인접한 정점들 중에 0인 정점이 있다면 승리하고, 아니면 패배한다.

 

근데 모든 시작점에 대해 이걸 다 구하기는 어렵다.

그래프가 아니라 트리라는 걸 이용하자.
1번 정점을 루트로 잡고 dfs로 색을 칠한다.

 

단 이때는, 자신의 부모노드는 고려하지 않은 채로 즉, 
인접한 정점들 중에 0인 정점을 살펴보는 것이 아니라,
자식 정점들 중에 0이 있는지 없는지를 살펴보자.

그리고 dp[x]마다, 자식노드에서 0인 것들의 개수를 저장한다.

 

그리고, dp2[x]를 새롭게 정의하자.

이 dp2[x]는 부모노드와 자신을 잇는 간선을 끊었을때 이길수 있는가?를 저장하고 있다.

그럼, 우리는 각 1~n까지 노드들을 iterate하면서 dp[x] 또는 dp2[x]가 1이상인지만 확인하면 된다.
dp2[x]를 채우는 방법은 유사하게 하는데, 부모노드의 dp[par]를 살펴보고, dp[x]가 0인지를 확인하면 O(1)에 판정할 수 있다.

따라서 tree dp 2개를 관리하면서 잘 하면 된다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<stack>
#include<map>
#include<set>
#include<deque>
#include<functional>
#include<unordered_map>
#include<list>
#include<cstdlib>
#include<ctime>

//#define double long double
//T.erase(unique(T.begin(),T.end()),T.end());
//written by djs100201
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 3e5 + 100, inf = 1e18, mod = 1e9 + 7, sqrtN = 333, p = 27, m_ = 55;
ll dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };
ll n, m, k, tc = 1, a, b, c, d, sum, x, y, z, w, base, ans;
ll gcd(ll x, ll y) {
	if (!y)return x;
	return gcd(y, x % y);
}
int A[n_], dp[n_], G[n_], Par[n_];
vector<int>v[n_];
ll f(ll x, ll par) {
	if (dp[x] != -1)return dp[x];
	ll ret = 0;
	for (auto nxt : v[x]) {
		if (nxt == par)continue;
		Par[nxt] = x;
		if (!f(nxt, x))ret++;
	}
	return dp[x] = ret;
}
ll g(ll x) {
	if (G[x] != -1)return G[x];
	ll ret = 0, par = Par[x];
	if (x!= 1 && g(par))return G[x] = 0;
	ret += f(par, x);
	if (!f(x, 0))ret--;
	return G[x] = (ret == 0);
}
void solve() {
	memset(dp, -1, sizeof(dp));
	memset(G, -1, sizeof(G));
	G[1] = 0;
	cin >> n;
	for (int i = 1; i < n; i++) {
		cin >> a >> b >> c;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	//cout << f(1, 0) << '\n';
	f(1, 0);
	for (int i = 1; i <= n; i++) {
		bool ok = false;
		if (f(i, 0) || g(i))cout << "Zeze";
		else cout << "Portuga";
		cout << '\n';
	}

}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	//cin >> tc;
	while (tc--)solve();
}