http://acm.hdu.edu.cn/showproblem.php?pid=6035
参考的大佬的博客。
附赠链接
http://blog.csdn.net/Bahuia/article/details/76141574
我觉得这道题，真是难。。
首先，反着求比较容易，我们可以先算出全集，然后减去每条路径中不出现的颜色数。
而不出现某种颜色，可以用类似虚数的思想，构建好多个只有相同颜色组建的树，而如果颜色不同的话，就不处理（这点体现在搜索上。一次搜索就能对好多颜色进行处理，我觉得关键是是color数组的应用。以及后来把color当下标。）
2 
具体的dfs过程是这样的。
维护一个 sum数组，保存当前搜索过程中 以i颜色为根的子树 总大小。（为什么酱紫呢，通过他们搜索回溯之间的差值我们可以计算出没一个 以相同颜色为根 之间的子树之间的差值。
比方说，可以计算出 9 和2 5。
）
然后我们计算出一个，就计算该区间片的路径大小（这些大小都是不包含颜色i的。因为他们被颜色i的节点挤压在一起。。。）
最后处理的过程中，我们发现 dfs最后一层，正好没有计算那么些 跨过 根节点的区间的路径，所以我们再加一次。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <bits/stdc++.h>
/* 一棵树，每个节点有自己的颜色，而每个节点之间共有
（n-1）*n/2条路径，问你每条路径包含的颜色和是多少。
在搜索的过程中，我们可以发现，可以通过反求 每条路径不包含多少。
我开始以为是 应该搜索完一株树完，然后我们就可以
*/
using namespace std;
const int maxn=200007;
const int mod=1e9+7;
typedef long long ll;
ll num[maxn];
ll siz[maxn];
ll color[maxn];
bool vis[maxn];
vector<int>G[maxn];
ll ans;
int dfs(int u,int las){
ll fh=0;
siz[u]=1;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==las) continue;
ll last=num[color[u]];
siz[u]+=dfs(v,u);//查询v子树中的大小。
ll cb=num[color[u]]-last;//这个子树中和当前节点一样的点。
ans+=((siz[v]-cb)*(siz[v]-cb-1)/2);//取一下mod
fh+=(siz[v]-cb);
}
num[color[u]]+=fh+1;//以u为底的子树的大小。
return siz[u];
}
int main()
{ int t;
int n;
int x;
int a,b;
int tt=1;
while(~scanf("%d",&n)){
memset(color,0,sizeof(color));
memset(num,0,sizeof(num));
memset(siz,0,sizeof(siz));
memset(vis,false,sizeof(vis));
ans=0;
int cnt=0;
for(int i=1;i<=n;i++){
scanf("%d",&color[i]);
//color[x]++;
if(!vis[color[i]]){
vis[color[i]]=true;
cnt++;
}
}
for(int i=0;i<maxn;i++)
G[i].clear();
for(int i=0;i<n-1;i++){
scanf("%d%d",&a,&b);
G[a].push_back(b);
G[b].push_back(a);
}
if(cnt==1){
printf("Case #%d: %lld\n",tt++,1ll*n*(1ll*n-1)/2);
continue;
}
dfs(1,-1);
//还要计算一些连通块跨越1节点的情况。
for(int i=1;i<=n;i++){
if(!vis[i]) continue;
ans+=(1ll*(n-num[i])*(n-num[i]-1)/2);
}
printf("Case #%d: %lld\n",tt++,1ll*(n*1ll*(n-1)*cnt)/2-ans);
}
return 0;
}