fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define NMAX 200005
  3. #define LOG 18
  4. using namespace std;
  5. struct edge{
  6.       int u ;
  7.       int limited;
  8.       int infinite ;
  9.  
  10. };
  11. int n;
  12. vector<edge> graph[NMAX];
  13. int high[NMAX],LCA[NMAX][LOG+1],cnt[NMAX];
  14. long long result=0;
  15. void enter()
  16. {
  17.     cin>>n;
  18.     for(int i=1;i<n;i++)
  19.     {
  20.         int u ,v,c1,c2;
  21.         cin>>u>>v>>c1>>c2;
  22.         graph[u].push_back({v,c1,c2});
  23.         graph[v].push_back({u,c1,c2});
  24.     }
  25. }
  26. void DFS(int top)
  27. {
  28.     for(edge bot:graph[top])
  29.     {
  30.         if(LCA[top][0]!=bot.u)
  31.         {
  32.             LCA[bot.u][0]=top;
  33.             high[bot.u]=high[top]+1;
  34.             DFS(bot.u);
  35.         }
  36.     }
  37. }
  38. void prepare()
  39. {
  40.     for(int j=1;j<=LOG;j++)
  41.     {
  42.         for(int i=1;i<=n;i++)
  43.         {
  44.             LCA[i][j]=LCA[LCA[i][j-1]][j-1];
  45.         }
  46.     }
  47. }
  48. int binary_lifting(int u ,int v)
  49. {
  50.     if(high[u]<high[v])
  51.     {
  52.         return binary_lifting(v,u);
  53.     }
  54.     for(int i=LOG;i>=0;i--)
  55.     {
  56.         if(high[u] - (1<<i) >= high[v])
  57.         {
  58.             u=LCA[u][i];
  59.         }
  60.     }
  61.     if(u==v)
  62.     {
  63.         return u;
  64.     }
  65.     for(int i=LOG;i>=0;i--)
  66.     {
  67.         if(LCA[u][i]!=LCA[v][i])
  68.         {
  69.             u=LCA[u][i];
  70.             v=LCA[v][i];
  71.         }
  72.     }
  73.     return LCA[u][0];
  74. }
  75. void DFS_result(int top)
  76. {
  77.     for(edge bot:graph[top])
  78.     {
  79.         if(LCA[top][0]!=bot.u)
  80.         {
  81.             DFS_result(bot.u);
  82.             cnt[top]+=cnt[bot.u];
  83.             result+=min(1ll*cnt[bot.u]*bot.limited,1ll*bot.infinite);
  84.         }
  85.     }
  86. }
  87. void process()
  88. {
  89.       for(int i=2;i<=n;i++)
  90.       {
  91.           cnt[i-1]++;
  92.           cnt[i]++;
  93.           cnt[binary_lifting(i,i-1)]-=2;
  94.       }
  95.       DFS_result(1);
  96.       cout<<result;
  97. }
  98. int main()
  99. {
  100.     ios_base::sync_with_stdio(0);
  101.     cin.tie(0);
  102.     cout.tie(0);
  103.     enter();
  104.     DFS(1);
  105.     prepare();
  106.     process();
  107.     return 0;
  108. }
  109.  
Success #stdin #stdout 0.01s 9380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5vd5mP
language:
C++14 (gcc 8.3)
created:
196 days 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!