Codeforces 902B - Coloring a Tree
題意:
你有一個有n個點的有根樹，根的編號為1，要為每個點上色，每個點的顏色為c1,c2,…cn，一開始每個點都沒顏色c = 0，你必須用「最少」的步驟來完成上色，每一步你能選擇任點v與任一顏色x，然後被選擇的點v與v的子樹顏色都會變成x，可以確定最後每個點都有顏色c != 0。
輸入n-1個數字p2,p3,…,pn代表第i個點與pi相連。
思路:
一棵樹上方會影響下方，所以就從第一個點看到最後，紀錄每個點當下是什麼顏色，對每一個點看這個點的上一個點是什麼顏色，如果是目標顏色就不用加一次步驟，並把當下顏色改成目標顏色。
程式碼:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| using namespace std; | |
| int main () | |
| { | |
| int n, p[10005], c[10005]; | |
| cin >> n; | |
| for (int i = 2;i <= n;i++) | |
| { | |
| cin >> p[i]; | |
| } | |
| for (int i = 1;i <= n;i++) | |
| { | |
| cin >> c[i]; | |
| } | |
| int ans = 1, nowColor[10005]; | |
| for (int i = 1;i <= n;i++) | |
| { | |
| nowColor[i] = c[1]; | |
| } | |
| for (int i = 2;i <= n;i++) | |
| { | |
| if (nowColor[p[i]] != c[i]) | |
| { | |
| ans++; | |
| } | |
| nowColor[i] = c[i]; | |
| } | |
| cout << ans << endl; | |
| return 0; | |
| } |