http://acm.hdu.edu.cn/showproblem.php?pid=6035

题意:有n(2e5)个结点的一棵树，每一个结点上都有一个颜色c[i],设一条路径的value为这天路径上点的颜色

的种类数，求树上所有路径的value和。

分析:树上所有路径，那显而易见是要算贡献的，那怎么算每个颜色/每个点对ans的贡献呢？首先看，要算每个点

对ans的贡献和很难算的,因为路径上还可以有同颜色的别的点呀，并且同颜色的点的个数还是不确定的，你想先算起来

再除也没有办法。于是可以算每个颜色对ans的贡献，因为不知道不包含某个颜色的路径有多少条，但是->->->

你是可以算出每个颜色对ans缺少多少贡献的，每个颜色对ans最多有C(n,2)点贡献，对于没有贡献的路径，就是不含有

任何一个颜色为c的点，这样是不是好求些了？是的。怎么求有多少个无效路径，可以把所有颜色为c的点扣掉，剩下就是很多

个连通块，对每一个连通块，设大小为sz，那么它可以产生颜色c对ans无贡献的路径的条数就为C(sz,2)

最后理论最多ans为 n*C(n,2)，减去每个颜色对ans缺少的贡献，就算出ans了

 

技巧:这里用到了一个“奇技淫巧”：

我之前怎么也没想到树形dp还能用来求树上连通块，这里就做到了对于结点，算是奇技淫巧吧，通过记录变量的增量，就可以

记录子结点中的一个增量，感觉所有的树上联通分块都可以这么搞，我也要加油！！！

 

代码转载于:https://blog.csdn.net/Bahuia/article/details/76141574

原作者的注释很详细，建议读者阅读参考:

下面是本蒟蒻的代码:

/////////////////////////////////////////Info/////////////////////////////////////////////////
//Problem:
//Date:
//Skill:
//Bug:
/////////////////////////////////////////Definations/////////////////////////////////////////////////
//循环控制
#define CLR(a) memset((a),0,sizeof(a))
#define F(i,a,b) for(int i=a;i<=int(b);++i)
#define F2(i,a,b) for(int i=a;i>=int(b);--i)
#define RE(i,n)  for(int i=0;i<int(n);i++)
#define RE2(i,n) for(int i=1;i<=int(n);i++)
//简化敲击
#define PII pair<int,int>
#define PDD pair<double,double>
#define PLL pair<long long ,long long>
#define PB push_back
#define MODY(n) (n%=mod)<0?n+=mod:n
#define MODED(n) ((n)<0?(n)%mod+mod:(n)%mod)
#define x first
#define y second
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const long long llinf = 0x3f3f3f3f3f3f3f3f;
////////////////////////////////////////Options//////////////////////////////////////////////////////
#define stdcpph
#define CPP_IO

#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#ifdef CPP_IO
#include<iostream>
#include<iomanip>
#include<string>
#else
#include<stdio.h>
#endif
#endif
////////////////////////////////////////Basic Functions//////////////////////////////////////////////
template<typename INint> inline void IN(INint &x)
{
	x = 0; int f = 1; char c; cin.get(c);
	while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
	while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
	x *= f;
}
template<typename INint> inline void OUT(INint x)
{
	if (x > 9)OUT(x / 10); cout.put(x % 10 + '0');
}
////////////////////////////////////////Added Functions//////////////////////////////////////////////
const int maxn = int(2e5+8);
int dom[maxn];
int sz[maxn];
int color[maxn];
ll ans(0);
ll n;
vector<int>G[maxn];
int dfs(int u, int p)
{
	sz[u] = 1;
	int inc_dom(1);
	int c = color[u];
	for (auto &v : G[u])if(v!=p)
	{
		int bef = dom[c];
		sz[u]+=dfs(v, u);
		int inc = dom[c] - bef;
		int block = sz[v]-(dom[c] - bef);
		ans += 1ll*(block - 1)*block / 2;
		inc_dom += block;
	}
	dom[c] += inc_dom;
	return sz[u];
}

////////////////////////////////////////////Code/////////////////////////////////////////////////////
int main()
{
	//freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
	int T(1), cas(0);
#ifdef CPP_IO// CPP_IO
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//cin >> T;
#else
	//IN(T);
#endif 
	/////////////////////////////////////////////////////////////////////////////////////////////////
	while ( T--,cin>>n)
	{
		F(i, 0, n)dom[i] = 0, G[i].clear(); ans = 0;
		F(i, 1, n)cin >> color[i];
		F(i, 1, n - 1)
		{
			int f, t; cin >> f >> t;
			G[f].PB(t); G[t].PB(f);
		}
		dfs(1, -1);
		F(i, 1, n)
		{
			int block = n - dom[i];
			ans +=1ll* block * (block - 1) / 2;
		}
		ans = 1ll*n * n*(n - 1) / 2 - ans;
		cout << "Case #"<<++cas<<": "<<ans << endl;
	}
	///////////////////////////////////////////////////////////////////////////////////////////////////
	return 0;
}
//What to Debug
/*
-1.最好把全部warning都X掉,否则:https://vjudge.net/solution/19887176
0.看看自己是否有可能需要快读，禁endl
1.数组越界，爆int,浮点精度(查看精度是否达到题目要求,看有没有浮点数比较:eps)，取模操作，初始化数组，边缘数据,输出格式(cas)
2.通读代码，代码无逻辑错误
3.读题，找到题意理解失误或算法错误
4.放弃
*/