@[zinuo](/user/104775) 能讲讲思路吗，我想做这题但不会做QwQ
by lion0514 @ 2020-10-24 07:54:26
~~蒟蒻的垃圾思路~~
## 就是先把从所有一个点开始的子树有几个节点算出来（可以记忆化）
```cpp
void dfs(int k){
use[k] = 1;
if(son[k][0] != -1){
dfs(son[k][0]);
use[k] += use[son[k][0]];
}
if(son[k][1] != -1){
dfs(son[k][1]);
use[k] += use[son[k][1]];
}
return;
}
```
## 再去判断从这个点的子树是否合法
```cpp
bool jub(int l, int r){
if(l == -1 && r == -1)
return 1;
if(l != -1 && r != -1
&& jub(son[l][0],son[r][1])
&& jub(son[l][1], son[r][0])
&& num[l] == num[r])
return 1;
return 0;
}
```
## 然后是代码
```
#include<cstdio>
#include<cstdlib>
typedef long long lld;
const lld N = 1000011;
lld son[N][2];
lld ans = -1, num[N], use[N];
lld n;
lld max(lld a, lld b) { return (a < b) ? b : a; }
lld read(){
lld x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-')
f = -1;
ch = getchar();
}
while('0' <= ch && ch <= '9'){
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
void dfs(int k){
use[k] = 1;
if(son[k][0] != -1){
dfs(son[k][0]);
use[k] += use[son[k][0]];
}
if(son[k][1] != -1){
dfs(son[k][1]);
use[k] += use[son[k][1]];
}
return;
}
bool jub(int l, int r){
if(l == -1 && r == -1)
return 1;
if(l != -1 && r != -1
&& jub(son[l][0],son[r][1])
&& jub(son[l][1], son[r][0])
&& num[l] == num[r])
return 1;
return 0;
}
int main(){
//freopen("tree.in", "r", stdin);
//freopen("tree.out", "w", stdout);
n = read();
for (int i = 1; i <= n; i++)
num[i] = read();
for (int i = 1; i <= n; i++)
son[i][0] = read(), son[i][1] = read();
dfs(1);
for (int i = 1; i <= n; i++)
if (jub(son[i][0], son[i][1]))
ans = max(ans, use[i]);
printf("%lld\n", ans);
}
```
## 不喜勿喷谢谢
by Soul_hunter @ 2020-11-04 10:13:33