Description

Input

Output

Sample Input

10
1 1 0 0 1 0 0 0 0 0
1 2
2 3
2 4
4 5
2 6
6 7
7 8
7 9
4 10

Sample Output

1 3 4 5 6

Data Constraint

Solution

• 首先，答案一定是唯一的，一個(gè)點(diǎn)不可能被標(biāo)記兩次。

• 考慮在樹(shù)中由下至上處理。

• 一個(gè)點(diǎn)的顏色如果和其父親相同，那么就不可能標(biāo)記這個(gè)點(diǎn)，不然就沒(méi)有貢獻(xiàn)。

• 那么我們討論與父親顏色不相同的情況。

• 如果自己是 黑色 ，父親是 白色 ，那么顯然標(biāo)記這個(gè)點(diǎn)，不然之后就不能再改到了。

• 如果自己是 白色 ，父親是 黑色 ，那么顯然也要標(biāo)記這個(gè)點(diǎn)，不然之后就不能統(tǒng)一修改了。

• 綜上所述，一個(gè)點(diǎn)的顏色如果和其父親相同，就直接標(biāo)記這個(gè)點(diǎn)。

• 注意特判根節(jié)點(diǎn)（我設(shè)為 1 號(hào)點(diǎn)），根節(jié)點(diǎn)為黑色的話也要標(biāo)記它。

• 于是我們把要標(biāo)記的點(diǎn)統(tǒng)計(jì)在一個(gè)桶里，順序輸出即可（快排都不用）。

• 時(shí)間復(fù)雜度是飛快的 O(N) 。

Code

#include<cstdio> using namespace std; const int N=5e5+1; bool a[N],ans[N]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } int main() {int n=read();for(int i=1;i<=n;i++) a[i]=read();ans[1]=a[1];for(int i=1;i<n;i++){int x=read(),y=read();if(a[x]!=a[y]) ans[y]=true;}for(int i=1;i<=n;i++)if(ans[i]) write(i),putchar(' ');return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5438. 【NOIP2017提高A组集训10.31】Tree的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。