首页 > 代码库 > cogs2478 简单的最近公共祖先 树形dp
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("%lld\n",ans); 44 } 45 int sb=haha(); 46 int main(){;}
cogs2478 简单的最近公共祖先 树形dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。