Promocao_OBI2020.cpp

#include<bits/stdc++.h>
using namespace std;

// Definimos o valor máximo de n para criar o vetor de adjacência
constexpr int maxn = 5e4+10;

using pii = pair<int, int>;

// Criamos o vetor do grafo
vector<pii> g[maxn]; // pair = {vizinhos, cor da aresta}

int ans = 0; // valor que salva qual o maior caminho (resposta)

// A dfs tem como parametros o indice do no atual e o pai (traverse normal de árvores)
// Ela retorna um pair, sendo o maior caminho saindo de uma aresta branco e de uma aresta preta
// branco -> 1, first // preto -> 0, second
pii dfs(int u, int p) {
	int maior_branco = 0, maior_preto = 0;

	for(auto nxt : g[u]) {
		int v = nxt.first, c = nxt.second;
		if(v == p) continue;

		// Perceba que nesse trecho selecionamos o que seria a cor oposta da dfs do filho v
		// e isso acontece pois como a ligação entre u -> v é branca (por exemplo)
		// queremos o maior caminho preto que sai de v, trocando as cores temos a mesma ideia
		if(c == 1)
			maior_branco = max(maior_branco, dfs(v, u).second);
		else
			maior_preto = max(maior_preto, dfs(v, u).first);
	}

	// Consideramos a resposta passando pelo nó atual
	// Precisamos adicionar 1 para também contar com o vértice atual
	ans = max(ans, maior_branco + maior_preto + 1);	

	// retornamos para o pai adicionando 1 para incluir o vértice atual
	return make_pair(maior_branco + 1, maior_preto + 1);
}

int main() {
	// Lemos a entrada e montamos o grafo
	int n; cin >> n;
	for(int i = 1; i < n; i++) {
		int u, v, c; cin >> u >> v >> c;
		g[u].push_back({v, c});
		g[v].push_back({u, c});
	}

	// enraizamos em 1 e começamos o processo
	dfs(1, -1);

	cout << ans << '\n';
}