Editorial for Another Tree Problem

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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
for i:=1 to n-1 do
begin
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;
}


#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);
for i:=1 to n-1 do
begin