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.
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 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.
Comments