結果
問題 | No.912 赤黒木 |
ユーザー |
![]() |
提出日時 | 2019-10-19 01:14:30 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 332 ms / 3,000 ms |
コード長 | 1,703 bytes |
コンパイル時間 | 711 ms |
コンパイル使用メモリ | 64,420 KB |
実行使用メモリ | 62,360 KB |
最終ジャッジ日時 | 2024-06-25 21:04:51 |
合計ジャッジ時間 | 9,082 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <iostream>#include <string>#include <algorithm>#include <vector>#define llint long long#define inf 1e18using namespace std;typedef pair<llint, llint> P;llint n;vector<llint> G[200005], g[200005];bool odd[200005];llint dp[200005][2][3];llint dp2[200005][2][3];void dfs(int v, int p, llint d){for(int i = 0; i < G[v].size(); i++){if(G[v][i] == p) continue;dfs(G[v][i], v, d+1);}for(int i = 0; i <= G[v].size(); i++){for(int j = 0; j < 2; j++){for(int k = 0; k <= 2; k++){dp2[i][j][k] = inf;}}}if(odd[v]) dp2[0][0][1] = 0, dp2[0][1][0] = d;else dp2[0][0][0] = 0;for(int i = 0; i < G[v].size(); i++){if(G[v][i] == p){for(int j = 0; j < 2; j++){for(int k = 0; k <= 2; k++){dp2[i+1][j][k] = dp2[i][j][k];}}continue;}int u = G[v][i];for(int j = 0; j < 2; j++){for(int k = 0; k <= 2; k++){for(int l = 0; l < 2; l++){for(int m = 0; m <= 2; m++){if(k+m > 2) continue;llint cost = 0;if(j+l >= 2) cost = 2*d;dp2[i+1][(j+l)%2][k+m] = min(dp2[i+1][(j+l)%2][k+m], dp2[i][j][k] + dp[u][l][m] - cost);}}}}}for(int j = 0; j < 2; j++){for(int k = 0; k <= 2; k++){dp[v][j][k] = dp2[(int)G[v].size()][j][k];}}}int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> n;llint u, v;for(int i = 0; i < n-1; i++){cin >> u >> v;G[u].push_back(v);G[v].push_back(u);}for(int i = 0; i < n-1; i++){cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}for(int i = 1; i <= n; i++){if((int)g[i].size() % 2) odd[i] = true;}dfs(1, -1, 0);cout << dp[1][0][2] + n-1 << endl;return 0;}