Spoj 3974 3974. Another Tree Problem<\/p>\n
Time Limit:1000MS Memory Limit:65536K
Total Submit:13 Accepted:2<\/p>\n
Description <\/strong><\/p>\n As you are bound to know by now, a tree is a connected graph Input <\/strong><\/p>\n The first line contains the integer N (2 \u2264 N \u2264 100 000), the number of vertices Output <\/strong><\/p>\n Output the weight of the tree, modulo 1000000007. <\/p>\n Sample Input <\/strong><\/p>\n 3 Sample Output <\/strong><\/p>\n 10200<\/p>\n Hint <\/strong><\/p>\n The weight of the path from 1 to 2 is 100 Source #include <vector> Spoj 3974 3974. Another Tree Problem Time Limit:1000MS Memory Limit:65536KTotal Submit:13 Accepted:2 Description As you are bound to know by now, a tree is a connected graph consisting of N vertices and N−1 edges. Trees also have the property of there being exactly a single unique path between any pair of vertices. You will be […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/310"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=310"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/310\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=310"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=310"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=310"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
consisting of N vertices and N−1 edges. Trees also have the property
of there being exactly a single unique path between any pair of
vertices.
You will be given a tree in which every edge is assigned a weight \u2013
a non negative integer. The weight of a path is the product of the
weights of all edges on the path. The weight of the tree is the sum of
the weights of all paths in the tree. Paths going in opposite
directions (A to B and B to A) are considered the same and, when
calculating the weight of a tree, are counted only once.
Write a program that, given a tree, calculates its weight modulo 1000000007. <\/p>\n
in the tree. The vertices are numbered 1 to N. Each of the following N−1
contains three integers A, B and W (1 \u2264 A, B \u2264 N, 0 \u2264 W \u2264 1000)
describing one edge. The edge connects vertices A and B, and its weight is W. <\/p>\n
3 2 100
2 1 100<\/p>\n
The weight of the path from 2 to 3 is 100
The weight of the path from 1 to 3 is 100 * 100 = 10000
So the weight of the tree is 10000 + 100 + 100 = 10200 <\/p>\n
\u9760\u3002\u3002\u7531\u4e8e\u6211\u6beb\u65e0\u667a\u5546\u3002\u3002\u3002\u8fd9\u4e2a\u9898\u76ee\u5f88\u663e\u7136Dfs\u4e00\u4e0b\u5c31\u53ef\u4ee5\u89e3\u51b3\u4e86\u3002\u3002\u4f46\u6211\u4ee5\u524d\u5c45\u7136\u5199\u4e2a\u6811\u7684\u5206\u6cbb\u53bb\u505a\u3002\u3002\u6211\u771f\u662f\u8111\u7f3a\u554a\u56e7\u3002\u3002\u3002\u3002
\u662f\u5728\u592a\u9119\u89c6\u81ea\u5df1\u4e86\u3002\u3002
Code\uff1a
<\/strong><\/p>\n
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define tr(e,x) for(eit e=x.begin();e!=x.end();e++)
const int inf=~0U>>1,maxn=100000,mod=1000000007;
using namespace std;
typedef long long ll;
int n;
struct Edge
{
int t,c;
Edge(int _t,int _c):t(_t),c(_c){}
};
vector<Edge> E[maxn];
typedef vector<Edge>::iterator eit;
void InsEdge(int s,int t,int c)
{
E[s].pb(Edge(t,c));E[t].pb(Edge(s,c));
}
ll pow(int x,int e)
{
if(!e)return 1;
ll tmp=pow(x,e\/2);tmp*=tmp;tmp%=mod;
if(e&1)tmp*=x,tmp%=mod;
return tmp;
}
ll Sum[maxn],P,ans=0;
int Q[maxn],F[maxn],h,t;
void BFS(int vs)
{
h=t=0;
for(Q[t++]=vs,F[vs]=-1;h<t;h++)
{
int x=Q[h];
tr(e,E[x])if(e->t!=F[x])
F[e->t]=x,Q[t++]=e->t;
}
for(int i=h-1;i>=0;i–)
{
int x=Q[i];Sum[x]=1;
ll all,tmp,ret=0;
tr(e,E[x])if(e->t!=F[x])
Sum[x]+=Sum[e->t]*e->c,Sum[x]%=mod;
all=Sum[x]+1;
tr(e,E[x])if(e->t!=F[x])
tmp=Sum[e->t]*e->c,tmp%=mod,ret+=(all-tmp)*tmp,ret%=mod;
ret*=P;ret%=mod;if(ret<0)ret+=mod;ans+=ret;ans%=mod;
}
}
int main()
{
\/\/freopen("in","r",stdin);
cin>>n;int s,t,c;
rep(i,n-1)
{
scanf("%d%d%d",&s,&t,&c);–s;–t;
InsEdge(s,t,c);
}
P=pow(2,mod-2);
BFS(0);
cout<<ans<<endl;
}<\/p>\n","protected":false},"excerpt":{"rendered":"