//?https://ac.nowcoder.com/acm/contest/31084/C

//?？透?jìng)賽題目講解_DongDong數(shù)顏色(樹(shù)上啟發(fā)式合并)

#include "stdafx.h"

//#include <bits/stdc++.h>

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

?

#include <vector>

#define LL long long

using namespace std;

int a[100005];//dfs序的顏色

int b[100005]={

0,1 ,4 ,2, 2

};//i節(jié)點(diǎn)的顏色

int c[100005];//顏色桶

int dfn[100005];//dfs序編號(hào)

int s[100005];//子樹(shù)節(jié)點(diǎn)個(gè)數(shù)

int son[100005];//重鏈節(jié)點(diǎn)

int ans[100005];

int now=0, T=0;

vector<int> G[100005];

void dfs(int u, int fa){//得到dfs序，和以u(píng)為根節(jié)點(diǎn)子樹(shù)節(jié)點(diǎn)個(gè)數(shù)

? ? s[u]=1; dfn[u]=++T;

//cout<<u<<",? ?son[u]="<<son[u]<<endl;

? ? for(auto x: G[u])

{

? ? ? ? if(x!=fa){

? ? ? ? ? ? dfs(x, u); s[u]+=s[x];

? ? ? ? ? ?// son[u]=s[x]>s[son[u]]?x:son[u];

//if(x==4)cout<<u<<",? s[x]="<<s[x]<<", son[u]="<<son[u]<<endl;

? ? ? ? }

? ? }

cout<<u<<"=u,? s[u]="<<s[u]<<endl;

}

void add(int u){//計(jì)算貢獻(xiàn)

//cout<<u<<"=u, c[u]="<<c[u]<<", !c[u]="<<!c[u]<<endl;

? ? now+=!c[u]++;//? 相同顏色只加一次

}

void DFS(int u, int fa ){//當(dāng)前節(jié)點(diǎn)， 父親節(jié)點(diǎn)?

? ? for(auto x: G[u]){//把 所有子樹(shù)的答案計(jì)算出來(lái)

? ? ? ? if(x!=fa)

{ // 計(jì)算子樹(shù)

? ? ? ? ? ? DFS(x, u);

? ? ? ? }

? ? }

? ? //計(jì)算u這棵樹(shù)的答案? ??

? ? ? ? ? ? for(int i=0; i<s[u]; i++){

? ? ? ? ? ? ? ? add(a[dfn[u]+i]);//子樹(shù)的dfs序是連續(xù)的

? ? ? ? ? ? }

????ans[u]=now;//把u自己加進(jìn)去

? ?

// 清空

? ? ? ? for(int i=now=0; i<s[u]; i++){

? ? ? ? ? ? c[a[dfn[u]+i]]=0;

? ? ? ? }? ? ?

}

int edge[32][2]={

1 ,4,

1 ,2,

2, 3

};

int main(){

? ? int n, m, x, y, q;

n=4;m=3;

//scanf("%d%d", &n, &m);

? ? for(int i=1; i<=n; i++){

? ? ? ?// scanf("%d", &b[i]);

? ? }

? ? for(int i=1; i<n; i++){

? ? ? ? //scanf("%d%d", &x, &y);

x=edge[i-1][0];

y=edge[i-1][1];

? ? ? ? G[x].push_back(y);

? ? ? ? G[y].push_back(x);

? ? }

? ? dfs(1, 0);

? ? for(int i=1; i<=n; i++){

cout<<dfn[i]<<",? ";

? ? ? ? a[dfn[i]]=b[i];

? ? }

cout<<endl<<" dfs number "<<endl;

? ? DFS(1, 0);

int qu[32]={4,2,1};

? ? while(m--){

? ? ? ?// scanf("%d", &q);

? ? ? ? printf("%d\n", ans[qu[m]]);

? ? }

? ? return 0;

}