Description:

现在有一棵被Samsara-Karma染了k种颜色的树，每种颜色有着不同的价值
Applese觉得Samsara-Karma染的太难看了，于是打算把整棵树重新染成同一种颜***r> 但是，由于一些奥妙重重的原因，每一次染色Applese可以选择两个有边相连的点，将其中一个染成另一个的颜色。而进行一次这样的操作需要付出两种颜色价值和的代价
现在，Applese的钱要用来买书(game)，所以他想要最小化代价

Input:

输入包括若干行
第一行包括一个数n，表示这棵树有n个节点
第二行包括n个数，第i个数表示第i个节点的颜色coli
**注意：一个颜色的标号即价值
接下来的n - 1行，每行包括两个数u, v，表示u节点与v节点之间有一条无向边
n ≤ 100000, 1 ≤ coli ≤ 1e9，数据保证是一棵树

Output:

输出包括一行
第一行包括一个数，表示最小代价

Sample Input:

4
2 3 4 3
1 2
2 3
3 4

Sample Output:

12

题目链接

这道题目只有一组输入数据，所以树中顶点的连接情况不用读入也不会对下一组数据产生影响（因为根本就不存在下一组数据）。
对每种颜色进行遍历，计算将整棵树改编为这种颜色的代价，取最小值即可。
代价计算方式为所有颜色之和-所遍历到的颜色×它的数量+除所遍历到的颜色以外其他颜色的数量×所遍历到的颜色。因为更新其他每个顶点的值都需要花费这个顶点的颜色+所遍历到的颜色代价。

AC代码:

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3+5;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
	int n;
	read(n);
	map<ll, int> cnt;
	set<ll> color;
	ll x, sum = 0;
	for (int i = 1; i <= n; ++i) {
		read(x);
		sum += x;
		cnt[x]++;
		color.insert(x);
	}
	ll ans = 1e18;
	for (auto i : color) {
		ans = min(ans, sum - cnt[i] * i + (n - cnt[i]) * i);
	} 
	printf("%lld\n", ans);
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("gedit out.txt");
#endif
    return 0;
}