Description

思源湖畔有一棵樹，那是獨(dú)孤玉溪最喜歡的地方。
傳說(shuō)中，這棵不見邊際的樹有N個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有1片葉子，每片葉子都擁有K種顏色中的一種，獨(dú)孤玉溪喜歡爬到這棵樹上，沿著一條路線摘葉子，并擁有所有顏色的葉子。
獨(dú)孤玉溪會(huì)選擇一個(gè)起點(diǎn)，并沿著樹邊走，然后最終停在一個(gè)終點(diǎn)上(起點(diǎn)和終點(diǎn)可能相同)，當(dāng)然了每一個(gè)結(jié)點(diǎn)只能經(jīng)過一次(每一片葉子只能摘一遍)。獨(dú)孤玉溪突生奇想，有多少種不同的方案能滿足自己呢？(兩種方案不同當(dāng)且僅當(dāng)起點(diǎn)不同或終點(diǎn)不同)。

Input

第一行包含兩個(gè)整數(shù)N和K。
第二行包含N個(gè)整數(shù)表示col[i]，為每片葉子的顏色(col[i]為1到K的一個(gè)整數(shù))。
第三行到第N+1行，每行有兩個(gè)整數(shù)x、y，表示x與y之間有一條樹邊。

Output

一行，表示求得的答案。

Sample Input

3 2
1 2 2
1 2
1 3

Sample Output

6

Data Constraint

20%的數(shù)據(jù)：N<=10000,K<=10
40%的數(shù)據(jù)：N<=50000,K<=2
100%的數(shù)據(jù)：N<=50000，K<=10

Solution

• 如果去掉顏色的限制，那么對(duì)于一棵N個(gè)節(jié)點(diǎn)的樹，

• 毫無(wú)疑問，它的路徑個(gè)數(shù)就是 N2 了。

• 現(xiàn)在有了顏色的限制，直接算不好算，但是K不大，可以考慮容斥。

• 枚舉哪些顏色不被選，剩下其它顏色可以選或不選。然后把這些顏色對(duì)應(yīng)的點(diǎn)全部刪去，

• 這樣得到一個(gè)森林，接下來(lái) O(N) 統(tǒng)計(jì)答案，最后乘上容斥系數(shù)即可。

• 只要會(huì)容斥原理，這種方法是沒什么理解難度的。

Code

#include<cstdio> #include<cstring> using namespace std; const int N=50001; int n,k,tot; long long ans,sum; int a[N],p[11]; int first[N],next[N*2],en[N*2]; bool bz[N]; inline int read() {int data=0; char ch=0;while(ch<'0' || ch>'9') ch=getchar();while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data; } inline void insert(int x,int y) {next[++tot]=first[x];first[x]=tot;en[tot]=y; } inline void find(int x,int s) {bz[x]=true;sum++;for(int i=first[x];i;i=next[i])if(!bz[en[i]] && !(s&p[a[en[i]]-1])) find(en[i],s); } inline void dfs(int x,int f,int s) {if(x==k){memset(bz,false,sizeof(bz));for(int i=1;i<=n;i++)if(!bz[i] && !(s&p[a[i]-1])){sum=0;find(i,s);ans+=f*sum*sum;}return;}dfs(x+1,f,s);dfs(x+1,-f,s+p[x]); } int main() {n=read(),k=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=p[0]=1;i<=k;i++) p[i]=p[i-1]*2;for(int i=1;i<n;i++){int x=read(),y=read();insert(x,y);insert(y,x);}dfs(0,1,0);printf("%lld",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5050. 【GDOI2017模拟一试4.11】颜色树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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