QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#105741 | #553. 王国 | zaneyu# | 100 ✓ | 124ms | 37656kb | C++23 | 4.4kb | 2023-05-15 10:35:04 | 2024-05-26 02:54:51 |
Judging History
answer
/*input
3
1 2 50
2 3 59
4
24 41 93
10 66 43
4
88 28 41
4 30 13
5
4 10 61 100
70 58 34 79
*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
//#pragma GCC target("avx2")
//order_of_key #of elements less than x
// find_by_order kth element
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll maxn=4e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-4;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
out<<P.f<<' '<<P.s;
return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?"\n":"");
return out;
}
ll mult(ll a,ll b){
return a*b%MOD;
}
ll mypow(ll a,ll b){
a%=MOD;
if(a==0) return 0;
if(b<=0) return 1;
ll res=1LL;
while(b){
if(b&1) res=(res*a)%MOD;
a=(a*a)%MOD;
b>>=1;
}
return res;
}
vector<pii> v[maxn];
vector<ll> l[maxn],c[maxn];
ll pf[maxn],p2[maxn],ppf[maxn];
int m;
ll get(int a,int b){
return pf[b]-pf[a];
}
int st[maxn];
ll ans=0;
int tot=0;
void dfs(int u,int p){
for(auto x:v[u]){
if(x.f==p) continue;
dfs(x.f,u);
st[u]+=st[x.f];
ans+=2LL*st[x.f]*(tot-st[x.f])%MOD*x.s%MOD;
ans%=MOD;
}
}
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int n;
cin>>n;
REP(i,n-1){
int a,b,c;
cin>>a>>b>>c;
--a,--b;
v[a].pb({b,c}),v[b].pb({a,c});
}
REP(i,n){
cin>>m;
--m;
tot+=m;
st[i]=m;
l[i].resize(2*m),c[i].resize(2*m);
REP(j,m){
cin>>l[i][j];
l[i][j+m]=l[i][j];
}
REP(j,m){
cin>>c[i][j];
c[i][j+m]=c[i][j];
}
REP1(j,2*m-1){
pf[j]=pf[j-1]+l[i][j-1];
ppf[j]=(ppf[j-1]+pf[j])%MOD;
MNTO(c[i][j],c[i][j-1]+l[i][j-1]);
}
for(int j=2*m-2;j>=0;j--){
MNTO(c[i][j],c[i][j+1]+l[i][j]);
}
REP(j,m) MNTO(c[i][j],c[i][j+m]),MNTO(c[i][j+m],c[i][j]);
p2[0]=c[i][0];
REP1(j,2*m-1){
p2[j]=p2[j-1]+c[i][j];
}
REP(j,m){
int a=j,b=j+m-1;
while(a<b){
int mid=(a+b+1)/2;
if(get(j,mid)<c[i][j]+c[i][mid]){
a=mid;
}
else b=mid-1;
}
int opl=a;
a=j+1,b=j+m;
while(a<b){
int mid=(a+b)/2;
if(get(mid,j+m)<c[i][j]+c[i][mid]){
b=mid;
}
else a=mid+1;
}
int opr=a;
if(opl<opr){
ans+=p2[opr-1]-p2[opl]+1LL*(opr-opl-1)*c[i][j];
ans+=(ppf[opl]-ppf[j])-1LL*(opl-j)*(pf[j]%MOD)%MOD;
ans+=pf[j+m]%MOD*(j+m-opr)%MOD-(ppf[j+m-1]-ppf[opr-1]);
}
else{
a=j,b=j+m;
while(a<b){
int mid=(a+b+1)/2;
if(get(j,mid)<get(mid,j+m)){
a=mid;
}
else b=mid-1;
}
ans+=(ppf[a]-ppf[j])-1LL*(a-j)*(pf[j]%MOD)%MOD;
++a;
ans+=1LL*(pf[j+m]%MOD)*(j+m-a)%MOD-(ppf[j+m-1]-ppf[a-1]);
}
ans%=MOD;
if(ans<0) ans+=MOD;
}
ans%=MOD;
}
REP(i,n){
int m=sz(c[i])/2;
REP(j,m) ans+=2LL*c[i][j]*(tot-m)%MOD;
ans%=MOD;
}
dfs(0,-1);
cout<<ans<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 2ms
memory: 7692kb
input:
10 1 2 50 2 3 59 2 4 73 1 5 79 4 6 10 1 7 66 1 8 43 4 9 4 8 10 30 8 39 2 72 38 78 95 10 45 98 29 59 98 5 32 10 46 36 43 69 61 95 96 14 7 76 99 100 13 58 9 69 31 63 9 43 83 68 96 72 91 39 17 66 53 22 13 2 32 58 91 14 41 36 73 96 55 90 6 24 14 39 21 67 27 80 7 99 20 24 61 27 7 71 95 45 35 95 10 64 45 ...
output:
1956394
result:
ok single line: '1956394'
Test #2:
score: 10
Accepted
time: 0ms
memory: 7768kb
input:
5 1 2 250 2 3 659 2 4 273 1 5 879 20 439 502 872 138 178 295 610 746 636 143 969 261 595 396 114 7 943 83 768 145 898 829 359 398 905 232 176 299 400 413 558 9 969 531 963 366 853 822 18 696 672 591 739 617 641 336 973 96 455 290 906 124 814 239 221 367 713 902 832 58 791 680 7 99 320 224 761 127 50...
output:
15675138
result:
ok single line: '15675138'
Test #3:
score: 10
Accepted
time: 9ms
memory: 9720kb
input:
10000 1 2 282475250 2 3 984943659 2 4 470211273 1 5 457850879 4 6 7237710 1 7 115438166 1 8 74243043 4 9 137522504 8 10 16531730 1 11 143542613 7 12 474833170 10 13 998097158 13 14 131570934 14 15 404280279 12 16 505795336 10 17 636807827 1 18 101929268 9 19 704877634 2 20 624379150 20 21 784558822 ...
output:
453173522
result:
ok single line: '453173522'
Test #4:
score: 10
Accepted
time: 55ms
memory: 28276kb
input:
100000 1 2 282475250 2 3 984943659 2 4 470211273 1 5 457850879 4 6 7237710 1 7 115438166 1 8 74243043 4 9 137522504 8 10 16531730 1 11 143542613 7 12 474833170 10 13 998097158 13 14 131570934 14 15 404280279 12 16 505795336 10 17 636807827 1 18 101929268 9 19 704877634 2 20 624379150 20 21 784558822...
output:
181864911
result:
ok single line: '181864911'
Test #5:
score: 10
Accepted
time: 22ms
memory: 14952kb
input:
1 100001 990117072 121266257 502101444 506187797 152265724 887855716 21575364 747489891 3913373 252828825 925488373 869945258 957255916 909604725 337241170 254650067 235485017 619901983 240912374 769328282 249600354 66310996 621433473 134246045 799368852 533841194 911465239 114696140 236494004 44433...
output:
672785783
result:
ok single line: '672785783'
Test #6:
score: 10
Accepted
time: 108ms
memory: 23816kb
input:
10 1 2 282475250 2 3 984943659 2 4 470211273 1 5 457850879 4 6 7237710 1 7 115438166 1 8 74243043 4 9 137522504 8 10 16531730 49733 22624218 300982665 75514183 17307023 151891674 818814124 681421086 983939896 975213637 388337097 728609775 503839345 909679593 275227646 722966525 313571842 143077312 3...
output:
5175380
result:
ok single line: '5175380'
Test #7:
score: 10
Accepted
time: 99ms
memory: 21184kb
input:
100 1 2 282475250 2 3 984943659 2 4 470211273 1 5 457850879 4 6 7237710 1 7 115438166 1 8 74243043 4 9 137522504 8 10 16531730 1 11 143542613 7 12 474833170 10 13 998097158 13 14 131570934 14 15 404280279 12 16 505795336 10 17 636807827 1 18 101929268 9 19 704877634 2 20 624379150 20 21 784558822 14...
output:
691155161
result:
ok single line: '691155161'
Test #8:
score: 10
Accepted
time: 91ms
memory: 23220kb
input:
1000 1 2 282475250 2 3 984943659 2 4 470211273 1 5 457850879 4 6 7237710 1 7 115438166 1 8 74243043 4 9 137522504 8 10 16531730 1 11 143542613 7 12 474833170 10 13 998097158 13 14 131570934 14 15 404280279 12 16 505795336 10 17 636807827 1 18 101929268 9 19 704877634 2 20 624379150 20 21 784558822 1...
output:
265274205
result:
ok single line: '265274205'
Test #9:
score: 10
Accepted
time: 75ms
memory: 24724kb
input:
10000 1 2 282475250 2 3 984943659 2 4 470211273 1 5 457850879 4 6 7237710 1 7 115438166 1 8 74243043 4 9 137522504 8 10 16531730 1 11 143542613 7 12 474833170 10 13 998097158 13 14 131570934 14 15 404280279 12 16 505795336 10 17 636807827 1 18 101929268 9 19 704877634 2 20 624379150 20 21 784558822 ...
output:
682655928
result:
ok single line: '682655928'
Test #10:
score: 10
Accepted
time: 124ms
memory: 37656kb
input:
100000 1 2 282475250 2 3 984943659 2 4 470211273 1 5 457850879 4 6 7237710 1 7 115438166 1 8 74243043 4 9 137522504 8 10 16531730 1 11 143542613 7 12 474833170 10 13 998097158 13 14 131570934 14 15 404280279 12 16 505795336 10 17 636807827 1 18 101929268 9 19 704877634 2 20 624379150 20 21 784558822...
output:
702441060
result:
ok single line: '702441060'