題意：
給一顆樹 每個節點有黑白2色
可以使一個色塊同事變色，問最少的變色次數。
思路：
先縮點 把一樣顏色的相鄰點 縮成一個
然后新的樹 剛好每一層是一個顏色。
最后的答案就是樹的直徑/2

不過我用的樹上的dp，強行求了以每個點為根時樹的深度
答案就是最小的深度-1

?

具體見代碼：

const int maxn = 200000 + 10; int n; int color[maxn]; int pa[maxn]; vector<int> G[maxn], G2[maxn]; void init() {scanf("%d", &n);for (int i = 1; i <= n; i++){scanf("%d", color + i);}int u, v;for (int i = 1; i < n; i++){scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u);} }int find(int x) { return pa[x] != x ? pa[x] = find(pa[x]) : x; }int fa[maxn]; void getTree() {queue<int> q;q.push(1);color[0] = -1;while (!q.empty()){int u = q.front(); q.pop();if (color[fa[u]] == color[u]) pa[u] = find(fa[u]);else G2[fa[pa[u]]].push_back(u);for (int i = 0; i < G[u].size(); i++){int v = G[u][i];if (find(v) == find(fa[u])) continue;fa[v] = pa[u];q.push(v);}}swap(G, G2); }void pg() {cout << "Graph:" << endl;for (int i = 0; i <= n; i++){for (int j = 0; j < G[i].size(); j++){cout << i << " " << G[i][j] << endl;}} }int son1[maxn], son2[maxn]; //i節點的最大的兒子 和 次大的兒子的下標int deep[maxn]; int deepFa[maxn];//i的父親除了i以外的最深深度int d[maxn];//以i為根時樹的深度 d[i] = max(deep[i], deepFa[i] + 1)int dfs(int u) //得到每個節點最深兒子的深度 {deep[u] = 0;for (int i = 0; i < G[u].size(); i++){int v = G[u][i];fa[v] = u;int tmp = dfs(v);if (tmp >= deep[u]){son2[u] = son1[u];son1[u] = v;deep[u] = tmp;}else{if (tmp > deep[son2[u]]) son2[u] = v;}}deep[u]++;return deep[u]; }int bfs() {queue<int> q;for (int i = 0; i < G[1].size(); i++) q.push(G[1][i]);int ans = d[1] = deep[1];while (!q.empty()){int u = q.front(); q.pop();if (son1[fa[u]] == u) deepFa[u] = deep[son2[fa[u]]] + 1;else deepFa[u] = deep[son1[fa[u]]] + 1;deepFa[u] = max(deepFa[u], deepFa[fa[u]] + 1);d[u] = max(deep[u], deepFa[u] + 1);ans = min(ans, d[u]);for (int i = 0; i < G[u].size(); i++){q.push(G[u][i]);}}return ans - 1; }void solve() {for (int i = 1; i <= n; i++) pa[i] = i;getTree();memset(fa, -1, sizeof(fa));for (int i = 0; i <= n; i++) son1[i] = son2[i] = n + 1;dfs(0);cout << bfs() << endl; }int main() {init();solve();return 0; }

?

轉載于:https://www.cnblogs.com/liangyongrui/p/6074008.html

總結

以上是生活随笔為你收集整理的Codeforces Round #379 (Div. 2) E. Anton and Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。