cogs2478 简单的最近公共祖先树形dp

80 阅读 0 评论 53 点赞

我是靠谱客的博主清秀咖啡豆，最近开发中收集的这篇文章主要介绍cogs2478 简单的最近公共祖先树形dp，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

填坑……链接：http://cogs.pro/cogs/problem/problem.php?pid=2478

题意：求出：。

日常题面不符系列……实际上这是个树归……从下向上，对于每个节点，他对于某个点做出的贡献就是子树的大小乘上（子树总大小减去这棵子树大小）再加上该点乘权值，用式子写就是$ans[root]=size[root]*(sum((size[root]-size[belong[v]]))+1)$。

递推即可。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn=1000005;
 7 struct node
 8 {
 9
int from,to,next;
10 }edge[maxn<<1];
11 int head[maxn],tot;
12 void addedge(int u,int v)
13 {
14
edge[++tot]=(node){u,v,head[u]};head[u]=tot;
15 }
16 int weight[maxn],n,size[maxn];
17 long long ans=0;
18 void dfs(int root)
19 {
20
size[root]=1;
21
for(int i=head[root];i;i=edge[i].next)
22 
{
23
int v=edge[i].to;
24
if(size[v])continue;
25 
dfs(v);
26
ans+=1ll*size[v]*1ll*weight[root]*1ll*size[root];
27
size[root]+=size[v];
28 
}
29
ans+=1ll*weight[root];
30 }
31 int haha()
32 {
33
freopen("easy_LCA.in","r",stdin);
34
freopen("easy_LCA.out","w",stdout);
35
scanf("%d",&n);
36
for(int i=1;i<=n;i++)scanf("%d",&weight[i]);
37
for(int i=1;i<n;i++)
38 
{
39
int x,y;scanf("%d%d",&x,&y);
40 
addedge(x,y);addedge(y,x);
41 
}
42
dfs(1);
43
printf("%lldn",ans);
44 }
45 int sb=haha();
46 int main(){;}