# 拉拉啦啦啦啦啦啦
嘿，有心情再看我這篇亂寫的東東._.
``` cpp=
#include <iostream>
#include <vector>
using namespace std;
vector <int> link[10005];
int now[10005];
int goal[10005];
int v[10005];
int dfs(int k)
{
int cnt=0;
if(now[k]!=goal[k])
{
now[k]=goal[k];
cnt++;
}
for(int j=0;j<link[k].size();j++)
{
int point;
link[k][j]=point;
for(int m=0;m<link[point].size();m++)
{
if(link[point][m]==0)
link[point][m]=1;
else if(link[point][m]==1)
link[point][m]=0;
}
}
for(int i = 0;i<link[k].size(); i++)
{
dfs(link[k][i]);
}
cout<<cnt<<endl;
return 0;
}
int main()
{
int n;
cin>>n;
int x,y;
for(int i=0;i<n;i++)
{
cin>>x>>y;
link[x].push_back(y);
link[y].push_back(x);
}
for(int i=0;i<n;i++) cin>>now[i];
for(int i=0;i<n;i++) cin>>goal[i];
dfs(1);
return 0;
}
```
1. 研究為什麼沒有輸出東西
可以先找找看程式卡在哪個地方，一個比較常見的方法就是在一些地方輸出(cout)東西。（這個方法在以後寫大型專案就比較不推薦了）
如果是我的話，我會先嘗試在第10行那邊先輸出看看，因為dfs比較容易出錯
``` cpp=9
int dfs(int k)
{
cout << k << endl;
...
}
```
應該會發現沒有印出東西，表示dfs沒有被執行到。那就再檢查執行dfs之前，看看哪邊有出錯，仔細看看會發現邊只要輸入n-1條所以把第41行改掉就會印出東西了。
``` cpp=41
for(int i = 0; i < n - 1; i++)
{
}
```
補充一下，一棵樹=>無向無環的結構，他會剛好有n-1條邊(n是點的數量)。
2. dfs的小問題
改好輸入問題，程式可能還是沒有照常運作，但沒關係，我們用前面的方法試試看，在第10行下面輸出k，看看dfs(int)是怎麼被呼叫的
那這邊就直接破梗，這邊寫反了拉XD
``` cpp=20
link[k][j]=point; // point = link[k][j]
```
改完之後，會發現有些點會重複走訪，也就是說，要記得紀錄哪些點走訪過，這樣就不會重複走到。比如說1和2之間有一條邊，那從1走到2之後，接著從點2繼續往下走，他會走回1。
這邊放個dfs的基本架構
``` cpp
void dfs(int u) {
visit[u] = true;
for(int v : e[u]) if(visit[v] == false) { // 還沒被走訪過的話，才繼續dfs
dfs(v);
}
}
```
那因為題目是給一棵樹，dfs由上到下，只會從父節點往下走，所以只要紀錄上一個節點是從哪裡來的，不要回到上一個節點，就沒問題了
``` cpp
void dfs(int u, int parent) {
for(int v : e[u]) if(v != parent) {
dfs(v, u);
}
}
```
再補充一下，這兩個寫法一樣喔
``` cpp
vector<int> v = {1, 2, 3, 4};
for(int i = 0; i < v.size(); i++) cout << v[i] << ' ';
for(int t : v) cout << t << ' ';
```
最後再提示一下解法，題目說，每次做更改，在當前節點下方，距離為偶數的節點也要做更改。
你的寫法看起來像是在每次做更改的時候，就把子樹做一次更新，原本你的下法理論上只會改到下下一層，不會對下下下下一層做更改。要對整個子樹做更新，就必須再做一次dfs，寫起來會像這樣
``` cpp
void dfs2(int k, int parent, int layer) {
if(layer % 2 == 0) { // 距離更改的點為偶數
if(now[k] == 0) now[k] = 1;
else if(now[k] == 1) now[k] = 0;
}
for(int u : link[k]) if(u != parent) {
dfs(u, k, layer + 1);
}
}
int dfs(int k, int parent)
{
int cnt=0;
if(now[k]!=goal[k])
{
// 不一樣，對子樹做更新
cnt++;
dfs2(k, parent, 0);
}
.
.
}
```
這個做法的時間複雜度會是$O(n^2)$，想像每次都要更新接近n個點，最多要更新約n次
那優化的部分就交給你再想一下了，好像分別紀錄深度為偶數和奇數的點，需要更新幾次就...
:D
Sign in with Wallet
Connect another wallet