四川省和城乡建设厅网站,wordpress 访问速度慢,2017网站趋势,网站设计师和ui设计师正题
P2664 题目大意
定义s(i,j)为i到j路径上的颜色数量#xff0c;sumi∑j1ns(i,j)sum_i\sum_{j1}^ns(i,j)sumi∑j1ns(i,j)
现在让你求sum的和 解题思路
考虑一种颜色的贡献#xff1a;
先把该颜色的点删掉#xff0c;这样就形成了若干小树
不难发现#xff0c;…正题
P2664 题目大意
定义s(i,j)为i到j路径上的颜色数量sumi∑j1ns(i,j)sum_i\sum_{j1}^ns(i,j)sumi∑j1ns(i,j)
现在让你求sum的和 解题思路
考虑一种颜色的贡献
先把该颜色的点删掉这样就形成了若干小树
不难发现同一小树中的点对不会产生贡献而不同小树的点对会产生一点贡献
那么在计算一个点的贡献时就是n-所在小树的size
那么直接dfs遍历每一个点然后计算
因为一个点只会影响当前颜色的贡献所以时间是O(n)的 code
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 100010
using namespace std;
ll n,x,y,now,tot,sum,f[N],p[N],h[N],c[N],sz[N],num[N],ans[N];
struct rec
{ll to,nx;
}e[N1];
void add(ll x,ll y)
{e[tot].toy;e[tot].nxh[x];h[x]tot;return;
}
void dfs1(ll x,ll fa)
{ll gnum[c[fa]];num[c[x]];sz[x]1;for(ll ih[x];i;ie[i].nx){ll ye[i].to;if(yfa)continue;dfs1(y,x);sz[x]sz[y];}if(fa)num[c[fa]](f[x]sz[x]-(num[c[fa]]-g));//计算小树大小return;
}
void dfs2(ll x,ll fa)
{ll gnum[c[fa]];nowf[x]-num[c[fa]];//减去上一小树大小num[c[fa]]f[x];ans[x]sum*n-nownum[c[x]];//当前结点颜色能不减for(ll ih[x];i;ie[i].nx){ll ye[i].to;if(yfa)continue;dfs2(y,x);}num[c[fa]]g;now-f[x]-num[c[fa]];return;
}
int main()
{scanf(%lld,n);for(ll i1;in;i){scanf(%lld,c[i]);if(!p[c[i]])p[c[i]]1,sum;}for(ll i1;in;i){scanf(%lld%lld,x,y);add(x,y);add(y,x);}dfs1(1,0);num[0]0;for(ll i1;i100000;i){if(!p[i])continue;num[i]n-num[i];nownum[i];}dfs2(1,0);for(ll i1;in;i)printf(%lld\n,ans[i]);return 0;
}
