Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const fi='';
      fo='';
      maxn=100010;
      z=1000000007;
var n:longint;   re,s:int64;
    a,c:array[1..maxn shl 1] of longint;
    b:array[1..maxn,0..2] of longint;
    pos,cur,sl:array[1..maxn] of longint;

procedure rf;
var i:longint;
begin
     read(n);
     for i:=1 to n-1 do
     begin
          read(b[i,0],b[i,1],b[i,2]);
          inc(sl[b[i,0]]);
          inc(sl[b[i,1]]);
     end;
     pos[1]:=1; cur[1]:=1;
     for i:=2 to n+1 do
     begin
          pos[i]:=pos[i-1]+sl[i-1];
          cur[i]:=pos[i];
     end;
     for i:=1 to n-1 do
     begin
          a[cur[b[i,0]]]:=b[i,1];
          c[cur[b[i,0]]]:=b[i,2];
          inc(cur[b[i,0]]);
          a[cur[b[i,1]]]:=b[i,0];
          c[cur[b[i,1]]]:=b[i,2];
          inc(cur[b[i,1]]);
     end;
end;

procedure visit(x,y:longint;var s:int64);
var i:longint;  sq,t:int64;
begin
     s:=0; sq:=0;
     for i:=pos[x] to pos[x+1]-1 do
         if a[i]<>y then
         begin
              visit(a[i],x,t);
              t:=(t*c[i]) mod z;
              re:=(re+(t*s) mod z) mod z;
              s:=(s+t) mod z;
         end;
     re:=(re+s) mod z;
     s:=(s+1) mod z;
end;

procedure pr;
var i:longint;
begin
     re:=0;
     visit(1,0,s);
     writeln(re);
end;

begin
     assign(input,fi); reset(input);
     rf;
     pr;
     close(input);
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<vector>
using namespace std;

const int N = (int) 1e5 + 5, TWO_POW_MINUS_ONE = (int) 5e8 + 4;
const long long MOD = (int) 1e9 + 7;
#define TR(v,i) for(typeof((v).begin()) i=(v).begin();i!=(v).end();++i)

long long a[N], b[N];
int n, c[N]; bool vst[N];
vector<vector<pair<int, int> > > g;

void enter() {
    scanf("%d", &n); g.resize(n);
    for(int i = 1; i < n; ++i) {
        int u, v, l; scanf("%d%d%d", &u, &v, &l);
        g[--u].push_back(make_pair(--v, l));
        g[v].push_back(make_pair(u, l));
    }
}

void dfs(int u) {
    vst[u] = 1;
    TR(g[u], it) {
        int v = it->first, w = it->second;
        if(vst[v]) continue; dfs(v); long long tmp = w * (a[v] + 1) % MOD;
        a[u] = (a[u] + tmp) % MOD;
        b[u] = (b[u] - tmp * tmp % MOD) % MOD;
    }
    b[u] = (b[u] + a[u] * a[u] % MOD) % MOD * TWO_POW_MINUS_ONE % MOD;
}

void solve() {
    dfs(0); long long res = 0;
    for(int i = 0; i < n; ++i) res = (res + a[i] + b[i]) % MOD;
    res = (res + MOD) % MOD;
    printf("%d\n", (int) res);
}

int main() {
    enter();
    solve();
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
const int N = 100005;
const long long B = 1000000007;
using namespace std;
vector<ii> a[N], child[N];
bool was[N];
long long P[N], Q[N], res;
int n;

void DFS(int u) {
    was[u] = true; int i, v;
    for(i=0; i<a[u].size(); i++) {
        v = a[u][i].X;
        if (was[v]) continue;
        child[u].push_back(a[u][i]);
        DFS(v);
    }
}

long long Pfunc(int u) {
    if (P[u] != -1) return P[u];
    P[u] = 0;
    int i, v; long long uv;
    for(i=0; i<child[u].size(); i++) {
        v = child[u][i].X; uv = child[u][i].Y;
        P[u] = (P[u] + (Pfunc(v) + 1) * uv) % B;
    }
    return P[u];
}

long long Qfunc(int u) {
    if (Q[u] != -1) return Q[u];
    int i, v;
    long long aa = 0, bb = 0, uv, tmp = 0;
    aa = Pfunc(u); aa = (aa * aa) % B;
    for(i=0; i<child[u].size(); i++) {
        v = child[u][i].X; uv = child[u][i].Y;
        tmp = ((Pfunc(v) + 1) * uv) % B;
        bb = (bb + tmp * tmp) % B;
    }
    tmp = (aa - bb + B) % B;
    if (tmp % 2 == 1) tmp += B;
    Q[u] = (tmp / 2) % B;
    return Q[u];
}

int main()
{
    scanf("%d\n", &n);
    int i, u, v, w;
    for(i=1; i<n; i++) {
        scanf("%d %d %d\n", &u, &v, &w);
        a[u].push_back(ii(v, w));
        a[v].push_back(ii(u, w));
        P[i] = Q[i] = -1;
    }
    P[n] = Q[n] = -1;
    DFS(1);
    long long res = 0;
    for(i=1; i<=n; i++)
        res = (res + Pfunc(i) + Qfunc(i)) % B;
    printf("%lld", res);
    return 0;
}

Code mẫu của RR

{$R+,Q+}
{$M 1000000}
//{$Mode objFPC}
const
  FINP='';
  FOUT='';
  MAXN=100001;
  oo=1000000007;
type
  list=^node;
  node=record
         u,c:longint;
         next:list;
       end;
var
  f1,f2:text;
  n:longint;
  ke:array[1..MAXN] of list;
  sum,sl:array[1..MAXN] of int64;
  xet:array[1..MAXN] of longint;
  kq:int64;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure add(u,c:longint; var a:list);
var
  p:list;
begin
  new(p); p^.u:=u; p^.c:=c;
  p^.next:=a; a:=p;
end;
procedure inp;
var
  i,u,v,c:longint;
begin
  read(f1,n);
  for i:=1 to n-1 do
    begin
      read(f1,u,v,c);
      add(u,c,ke[v]);
      add(v,c,ke[u]);
    end;
end;
procedure ans;
begin
  if kq mod 2=0 then writeln(f2,kq div 2)
  else writeln(f2,(kq+oo) div 2);
end;
procedure dfs1(u:longint);
var
  v:longint;
  c:int64;
  p:list;
begin
  xet[u]:=1;
  sl[u]:=0; sum[u]:=0;
  p:=ke[u];
  while p<>nil do
    begin
      v:=p^.u; c:=p^.c; p:=p^.next;
      if xet[v]=1 then continue;
      dfs1(v);
      sl[u]:=sl[u]+sl[v]+1;
      sum[u]:=(sum[u]+c+sum[v]*c) mod oo;
    end;
end;
procedure dfs2(u:longint);
var
  v:longint;
  x,y,c:int64;
  p:list;
begin
  xet[u]:=1;
  p:=ke[u];
  while p<>nil do
    begin
      v:=p^.u; c:=p^.c; p:=p^.next;
      if xet[v]=1 then continue;
      dfs2(v);
      x:=(c*(sum[v]+1)) mod oo;
//      try
      y:=(sum[u]-(c*(sum[v]+1)) mod oo) mod oo;
//      except writeln(c,' ',sum[v],' ',sum[u]); halt; end;
      kq:=(kq+x*y) mod oo;
    end;
  kq:=(kq+sum[u]*2) mod oo;
end;
begin
  openF;
  inp;
  dfs1(1);
  fillchar(xet,sizeof(xet),0);
  dfs2(1);
  ans;
  closeF;
end.

Code mẫu của hieult

#include <vector>
#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;
}

Code mẫu của ll931110

#include <cstring>
#include <iostream>
#include <vector>
#define mod 1000000007
using namespace std;

int pr[100010];
int n;
long long top[100010],bot[100010];
long long ret = 0;
vector< pair<int,int> > adj[100010];

void DFS(int u)
{
    for (vector< pair<int,int> >::iterator iter = adj[u].begin(); iter != adj[u].end(); iter++)
    {
        int v = iter->first;
        if (pr[v] > -1) continue;
        pr[v] = u;
        DFS(v);
    }
}

void DFScalc(int u)
{
    for (vector< pair<int,int> >::iterator iter = adj[u].begin(); iter != adj[u].end(); iter++)
    {
        int v = iter->first;
        if (pr[u] == v) continue;
        top[v] = (1LL * (top[u] + 1) * iter->second) % mod;
        DFScalc(v);
        long long tmp = (1LL * (bot[v] + 1) * iter->second) % mod;
        ret = (ret + bot[u] * tmp) % mod;
        bot[u] = (bot[u] + tmp) % mod;
    }
}

int main()
{
//  freopen("putevi.in","r",stdin);
//  freopen("putevi.out","w",stdout);
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int x,y,c;
        scanf("%d %d %d", &x, &y, &c);
        adj[x].push_back(make_pair(y,c));
        adj[y].push_back(make_pair(x,c));
    }
    memset(pr,-1,sizeof(pr));
    memset(top,0,sizeof(top));
    memset(bot,0,sizeof(bot));
    pr[1] = 0;
    DFS(1);
    DFScalc(1);
    for (int i = 1; i <= n; i++) ret = (ret + top[i]) % mod;
    cout << ret << endl;
}

Code mẫu của skyvn97

#include<cstdio>
#include<vector>
#include<cstring>
#define MAX   100100
#define p   first
#define s   second
using namespace std;
typedef long long ll;
const ll mod=(ll)1e9+7;
typedef pair<int,ll> ii;
vector<ii> g[MAX];
int c[MAX];
int n;
ll f[MAX];
ll res;
void loadgraph(void) {
    int i;
    int u,v;
    ll cst;
    scanf("%d",&n);
    for (i=1;i<=n;i=i+1) g[i].clear();
    for (i=1;i<n;i=i+1) {
        scanf("%d",&u);
        scanf("%d",&v);
        scanf("%lld",&cst);
        g[u].push_back(ii(v,cst));
        g[v].push_back(ii(u,cst));
    }
    memset(f,0,sizeof f);
    memset(c,0,sizeof c);
    res=0;
}
void visit(const int &u) {
    int i,v;
    //printf("Visiting %d\n",u);
    for (i=0;i<g[u].size();i=i+1)
        if (c[g[u][i].p]==0) {
            v=g[u][i].p;
            c[v]=1;
            visit(v);
            //printf("f(%d)=%lld\n",v,f[v]);
            res=(res+f[v])%mod;
            res=(res+((f[v]*g[u][i].s+g[u][i].s)%mod)*f[u])%mod;
            f[u]=(f[u]+f[v]*g[u][i].s+g[u][i].s)%mod;
            //printf("res is now %lld\n",res);
        }
}
void process(void) {
    c[1]=1;
    visit(1);
    printf("%lld",(res+f[1])%mod);
}
int main(void) {
    loadgraph();
    process();
    return 0;
}

Code mẫu của khuc_tuan

//{$A8,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O+,P+,Q+,R+,S+,T-,U-,V+,W-,X+,Y+,Z1}
// {$APPTYPE CONSOLE}
 {$mode delphi}
{$M 16777216}

const
    modulo = 1000000007;

type
    List = class
        i, w : integer;
        n : List;
    end;

function POW(x,n : integer) : integer;
var
    t : integer;
begin
    if n=0 then begin POW := 1; exit; end;
    t := POW(x,n div 2);
    if n mod 2 = 0 then POW := int64(t) * t mod modulo
    else POW := int64(t) * t mod modulo * x mod modulo;
end;

procedure AddList(var l : List; i, w : integer);
var
    q : List;
begin
    q := List.Create;
    q.i := i;
    q.w := w;
    q.n := l;
    l := q;                
end;

var
    ke : array[1..100000] of List;
    i, u, v, w, n : integer;
    chia2 : integer;
    f, g : array[1..100000] of int64;
    father : array[1..100000] of integer;


procedure dfs(i : integer);
var
    p : List;
    z, j, w : integer;
    tong, tong2 : integer;
begin
    p := ke[i];
    tong := 0;
    tong2 := 0;
    while p<>nil do
    begin
        j := p.i;
        w := p.w;
        p := p.n;
        if father[i]<>j then
        begin
            father[j] := i;
            dfs(j);
            f[i] := (f[i] + f[j]) mod modulo;
            z := int64(w) * g[j] mod modulo;
            tong := (tong + z) mod modulo;
            tong2 := (tong2 + int64(z) * z mod modulo) mod modulo;
        end;
    end;

        g[i] := (tong + 1) mod modulo;
        f[i] := (f[i] + (int64(tong) * tong + modulo - tong2) mod modulo * chia2) mod modulo;
        f[i] := (f[i] + tong) mod modulo;
end;

begin
    chia2 := POW(2, modulo - 2);
    read(n);
    for i:=1 to n-1 do
    begin
        read(u,v,w);
        AddList(ke[u],v,w);
        AddList(ke[v],u,w);
    end;
    dfs(1);
    writeln(f[1]);
end.