---
# System prepended metadata

title: 拉拉啦啦啦啦啦啦

---

# 拉拉啦啦啦啦啦啦
嘿，有心情再看我這篇亂寫的東東._.
``` 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