/acm/contest/133/A
题意：就是给出一棵树，每个节点都有价值，问把所有节点都改成一种价值的最小花费，改一条边的两个节点所需的花费是两个节点的和。
方法：一开始想得是O(n*n)的算法，就是把所有点跑一遍，取小的，不用想，肯定TLE，然后优化，先统计输入数的和，那么第二个for就可以优化，变成O(n).
输入的数太大，不能用数组存来计算每个数出现的次数，怎么办？
用map来弄
数大，那就用去重后，这个数的位置代表这个数，mp储存的是这个数的位置
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=100005;map<ll,int>mp;ll a[maxn],c[maxn],v[maxn];int main(){int n,i,j,x,y,cnt,l;ll sum,minn,temp;scanf("%d",&n);sum=0;cnt=1;for(i=1;i<=n;i++){scanf("%lld",&a[i]);sum+=a[i];if(mp.find(a[i])!=mp.end())//出现过{v[mp[a[i]]]++;}else{mp[a[i]]=cnt;//此数的位置v[cnt]=1;//此位置出现的次数，即是这个数出现的位置c[cnt]=a[i];//去重cnt++;}}for(i=1;i<=n-1;i++)scanf("%d%d",&x,&y);minn=sum-c[1]*v[1]+(n-(v[1]))*c[1];for(i=2;i<cnt;i++){temp=sum-c[i]*v[i]+(n-v[i])*c[i];minn=min(minn,temp);}printf("%lld\n",minn);}
如果觉得《染色（方法：要统计每个数出现的次数 而这个数很大 用数组存不了 怎么弄？)》对你有帮助，请点赞、收藏，并留下你的观点哦！
