fork download 
  1. #pragma GCC optimize("O3")
  2. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  3. #pragma GCC optimize("unroll-loops")
  4. #include <bits/stdc++.h>
  5.  
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define files(name) name!=""?freopen(name".in","r",stdin),freopen(name".out","w",stdout):0
  8. #define all(a) a.begin(),a.end()
  9. #define len(a) (int)(a.size())
  10. #define elif else if
  11. #define mp make_pair
  12. #define pb push_back
  13. #define fir first
  14. #define sec second
  15.  
  16. using namespace std;
  17. #define int long long
  18.  
  19. typedef unsigned long long ull;
  20. typedef pair<int,int> pii;
  21. typedef vector<int> vi;
  22. typedef long double ld;
  23. typedef long long ll;
  24.  
  25. const int arr=2e5+10;
  26. const int ar=2e3+10;
  27. const ld pi=acos(-1);
  28. const ld eps=1e-10;
  29. const ll md=1e9+7;
  30.  
  31. ///---program start---///
  32.  
  33. struct line
  34. {
  35.     ld k,b;
  36.     set<line>::iterator it;
  37.     set<line>* where;
  38.  
  39.     line() {}
  40.     line(ld k,ld b)
  41.     {
  42.         this->k=k;
  43.         this->b=b;
  44.     }
  45.  
  46.     ld eval(ld x)
  47.     {
  48.         return k*x+b;
  49.     }
  50. };
  51.  
  52. const bool operator<(const line& lhs,const line& rhs)
  53. {
  54.     if (rhs.k==5e18){
  55.         auto it=lhs.it;
  56.         return next(it)!=lhs.where->end()&&next(it)->k*rhs.b+next(it)->b<=it->k*rhs.b+it->b;
  57.     }
  58.     return lhs.k>rhs.k||(lhs.k==rhs.k&&lhs.b<rhs.b);
  59. }
  60.  
  61. ld intersect(line l1,line l2)
  62. {
  63.     /// l1.k*x+l1.b==l2.k*x+l2.b
  64.     /// x*(l1.k-l2.k)==l2.b-l1.b
  65.     /// x==(l2.b-l1.b)/(l1.k-l2.k)
  66.     return (l2.b-l1.b)/(l1.k-l2.k);
  67. }
  68.  
  69. bool to_erase(line l1,line l2,line l3)
  70. {
  71.     ld x=intersect(l1,l2);
  72.     return l2.eval(x)>=l3.eval(x);
  73. }
  74.  
  75. struct convex_hull_trick
  76. {
  77.     set<line> lines;
  78.  
  79.     convex_hull_trick()
  80.     {
  81.         lines.clear();
  82.     }
  83.  
  84.     void clear()
  85.     {
  86.         lines.clear();
  87.     }
  88.     void add_line(line l)
  89.     {
  90.         auto it=lines.insert(l).fir;
  91.  
  92.         line* what=(line*)&*it;
  93.         what->it=it;
  94.         what->where=(set<line>*)&lines;
  95.  
  96.         while (it!=lines.begin()&&prev(it)->k==it->k){
  97.             lines.erase(it);
  98.             return;
  99.         }
  100.  
  101.         while (next(it)!=lines.end()&&next(it)->k==it->k){
  102.             lines.erase(next(it));
  103.         }
  104.  
  105.         if (it!=lines.begin()&&next(it)!=lines.end()&&to_erase(*prev(it),*it,*next(it))){
  106.             lines.erase(it);
  107.             return;
  108.         }
  109.  
  110.         while (it!=lines.begin()&&prev(it)!=lines.begin()&&to_erase(*prev(prev(it)),*prev(it),*it)){
  111.             lines.erase(prev(it));
  112.         }
  113.  
  114.         while (next(it)!=lines.end()&&next(next(it))!=lines.end()&&to_erase(*it,*next(it),*next(next(it)))){
  115.             lines.erase(next(it));
  116.         }
  117.     }
  118.  
  119.     ld get(ld x)
  120.     {
  121.         if (lines.empty()){
  122.             return 5e18;
  123.         }
  124.         line special(5e18,x);
  125.         auto it=*lines.lower_bound(special);
  126.         return it.eval(x);
  127.     }
  128. };
  129.  
  130. struct segment_tree
  131. {
  132.     int n;
  133.     vector<convex_hull_trick> t;
  134.  
  135.     segment_tree() {}
  136.     segment_tree(int n)
  137.     {
  138.         n++;
  139.         this->n=n;
  140.         t.resize(4*n);
  141.     }
  142.  
  143.     void upd(int v,int l,int r,int tl,int tr,line val)
  144.     {
  145.         if (l>tr||r<tl){
  146.             return;
  147.         }
  148.         if (l>=tl&&r<=tr){
  149.             t[v].add_line(val);
  150.             return;
  151.         }
  152.         int m=(l+r)/2;
  153.         upd(v*2,l,m,tl,tr,val);
  154.         upd(v*2+1,m+1,r,tl,tr,val);
  155.     }
  156.     void upd(int tl,int tr,line val)
  157.     {
  158.         upd(1,1,n,tl,tr,val);
  159.     }
  160.     ld get(int v,int l,int r,int pos,ld x)
  161.     {
  162.         if (l==r){
  163.             return t[v].get(x);
  164.         }
  165.         ld res=t[v].get(x);
  166.         int m=(l+r)/2;
  167.         if (pos<=m){
  168.             res=min(res,get(v*2,l,m,pos,x));
  169.         }
  170.         else{
  171.             res=min(res,get(v*2+1,m+1,r,pos,x));
  172.         }
  173.         return res;
  174.     }
  175.     ld get(int pos,ld x)
  176.     {
  177.         return get(1,1,n,pos,x);
  178.     }
  179. };
  180.  
  181. #define arr (int)(5e5+10)
  182.  
  183. vector<pii> reb[arr];
  184. const int M=20;
  185. int p[arr][M];
  186. ld d[arr];
  187. int deep[arr];
  188. int cnt[arr];
  189. int go_hld[arr];
  190.  
  191. void dfs(int now,int pred=-1)
  192. {
  193.     p[now][0]=pred;
  194.     for (int i=1;i<M;i++){
  195.         p[now][i]=p[p[now][i-1]][i-1];
  196.     }
  197.     cnt[now]=1;
  198.     go_hld[now]=-1;
  199.     for (auto wh:reb[now]){
  200.         if (wh.fir!=pred){
  201.             deep[wh.fir]=deep[now]+1;
  202.             d[wh.fir]=d[now]+wh.sec;
  203.             dfs(wh.fir,now);
  204.             cnt[now]+=cnt[wh.fir];
  205.             if (go_hld[now]==-1||cnt[wh.fir]>cnt[go_hld[now]]){
  206.                 go_hld[now]=wh.fir;
  207.             }
  208.         }
  209.     }
  210. }
  211.  
  212. int lca(int u,int v)
  213. {
  214.     if (deep[u]>deep[v]){
  215.         swap(u,v);
  216.     }
  217.     for (int i=M-1;i>=0;i--){
  218.         if (deep[p[v][i]]>=deep[u]){
  219.             v=p[v][i];
  220.         }
  221.     }
  222.     if (u==v){
  223.         return u;
  224.     }
  225.     for (int i=M-1;i>=0;i--){
  226.         if (p[u][i]!=p[v][i]){
  227.             u=p[u][i];
  228.             v=p[v][i];
  229.         }
  230.     }
  231.     return p[u][0];
  232. }
  233.  
  234. int len_of_way[arr];
  235. int top_of_way[arr];
  236. int back_of_way[arr];
  237. int number_of_way[arr];
  238. segment_tree S;
  239. vector<line> to_push_on_prefix[arr];
  240.  
  241. int pos_in_segment_tree[arr];
  242. int who_with_pos[arr];
  243.  
  244. int current_number_of_way;
  245. int current_pos_in_segment_tree;
  246.  
  247. void hld(int now,int pred)
  248. {
  249.     pos_in_segment_tree[now]=++current_pos_in_segment_tree;
  250.     who_with_pos[pos_in_segment_tree[now]]=now;
  251.     number_of_way[now]=current_number_of_way;
  252.     if (!top_of_way[current_number_of_way]){
  253.         top_of_way[current_number_of_way]=now;
  254.     }
  255.     len_of_way[number_of_way[now]]++;
  256.     back_of_way[current_number_of_way]=now;
  257.  
  258.     if (go_hld[now]!=-1){
  259.         hld(go_hld[now],now);
  260.     }
  261.     for (auto wh:reb[now]){
  262.         if (wh.fir!=pred&&wh.fir!=go_hld[now]){
  263.             current_number_of_way++;
  264.             hld(wh.fir,now);
  265.         }
  266.     }
  267. }
  268.  
  269. void add_line_to_mini_way(int u,int v,line l) /// v is pred u
  270. {
  271.     if (top_of_way[number_of_way[u]]==v){
  272.         to_push_on_prefix[pos_in_segment_tree[u]].pb(l);
  273.     }
  274.     else{
  275.         int tl=pos_in_segment_tree[v];
  276.         int tr=pos_in_segment_tree[u];
  277.         S.upd(tl,tr,l);
  278.     }
  279. }
  280.  
  281. void add_line_to_way(int u,int v,line l) /// v is pred u
  282. {
  283.     while (number_of_way[u]!=number_of_way[v]){
  284.         int to=top_of_way[number_of_way[u]];
  285.         add_line_to_mini_way(u,to,l);
  286.         u=p[to][0];
  287.     }
  288.     add_line_to_mini_way(u,v,l);
  289. }
  290.  
  291. void add_way(int u,int v,ld t,ld s)
  292. {
  293.     int LCA=lca(u,v);
  294.     line line1=*new line(-ld(1)/ld(s),ld(d[u])/s+t);
  295.     add_line_to_way(u,LCA,line1);
  296.     line line2=*new line(+ld(1)/ld(s),ld(d[u]-2*d[LCA])/s+t);
  297.     add_line_to_way(v,LCA,line2);
  298. }
  299.  
  300. int n;
  301. ld ans[arr];
  302.  
  303. void build_all_ans()
  304. {
  305.     for (int i=1;i<=n;i++){
  306.         ans[i]=S.get(pos_in_segment_tree[i],d[i]);
  307.     }
  308.     convex_hull_trick CHT;
  309.     for (int i=0;i<=current_number_of_way;i++){
  310.         CHT.clear();
  311.         int cur=back_of_way[i];
  312.         for (int j=0;j<len_of_way[i];j++){
  313.             for (auto k:to_push_on_prefix[pos_in_segment_tree[cur]]){
  314.                 CHT.add_line(k);
  315.             }
  316.             ans[cur]=min(ans[cur],CHT.get(d[cur]));
  317.             cur=p[cur][0];
  318.         }
  319.     }
  320. }
  321.  
  322. void solve()
  323. {
  324.     cin>>n;
  325.  
  326.     for (int i=0;i<=n;i++){
  327.         reb[i].clear();
  328.         ans[i]=0;
  329.         len_of_way[i]=0;
  330.         top_of_way[i]=0;
  331.         back_of_way[i]=0;
  332.         number_of_way[i]=0;
  333.         to_push_on_prefix[i].clear();
  334.         pos_in_segment_tree[i]=0;
  335.         who_with_pos[i]=0;
  336.         d[i]=0;
  337.         deep[i]=0;
  338.         cnt[i]=0;
  339.         go_hld[i]=-1;
  340.     }
  341.     current_number_of_way=0;
  342.     current_pos_in_segment_tree=0;
  343.  
  344.     for (int i=1;i<n;i++){
  345.         int u,v,w;
  346.         cin>>u>>v>>w;
  347.         reb[u].pb({v,w});
  348.         reb[v].pb({u,w});
  349.     }
  350.     dfs(1,1);
  351.     hld(1,1);
  352.     S=*new segment_tree(n);
  353.     int m;
  354.     cin>>m;
  355.     while (m--){
  356.         int u,v,t,s;
  357.         cin>>u>>v>>t>>s;
  358.         add_way(u,v,t,s);
  359.     }
  360.     build_all_ans();
  361.     for (int i=1;i<=n;i++){
  362.         if (ans[i]==5e18){
  363.             cout<<-1<<"\n";
  364.         }
  365.         else{
  366.             cout<<fixed<<setprecision(7)<<ans[i]<<"\n";
  367.         }
  368.     }
  369. }
  370.  
  371. main()
  372. {
  373.     #ifdef I_love_Maria_Ivanova
  374.         files("barik");
  375.         freopen("debug.txt","w",stderr);
  376.     #endif
  377.  
  378.     fast;
  379.  
  380.     int test;
  381.     cin>>test;
  382.     while (test--){
  383.         solve();
  384.     }
  385. }
Success #stdin #stdout 0.02s 26772KB
comments ()
stdin 
1
5
1 2 3
1 3 5
3 4 1
4 5 4
3
2 1 3 4
4 2 1 3
1 3 2 6
stdout 
2.0000000
3.0000000
1.3333333
1.0000000
-1
https://ideone.com/3fcEa0
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!