fork download
copy 
  1. using System;
  2. using System.IO;
  3. using System.Linq;
  4.  
  5. using ll = System.Int64;
  6.  
  7. class vinh
  8. {
  9.     static void uia()
  10.     {
  11.         int n = uiia.cin();
  12.         if(n == 0) return;
  13.         int k = uiia.cin();
  14.  
  15.         ll[] a = new ll[n + 1];
  16.         for(int i = 1; i <= n; i++){
  17.             a[i] = uiia.nl();
  18.         }
  19.  
  20.         int[] head = new int[n + 1];
  21.         int[] to = new int[2 * n + 5];
  22.         ll[] we = new ll[2 * n + 5];
  23.         int[] next = new int[2 * n + 5];
  24.         int cd = 1;
  25.  
  26.         for(int i = 1; i < n; i++){
  27.             int u = uiia.cin();
  28.             int v = uiia.cin();
  29.             ll w = uiia.nl();
  30.  
  31.             to[cd] = v;
  32.             we[cd] = w;
  33.             next[cd] = head[u];
  34.             head[u] = cd++;
  35.  
  36.             to[cd] = u;
  37.             we[cd] = w;
  38.             next[cd] = head[v];
  39.             head[v] = cd++;
  40.         }
  41.  
  42.         int[] bgb = new int[n + 1];
  43.         int[] de = new int[n + 1];
  44.         int dd = 0;
  45.  
  46.         int[] q = new int[n + 1];
  47.         int h = 0, t = 0;
  48.  
  49.         q[t++] = 1;
  50.         bgb[1] = 0;
  51.  
  52.         while(h < t){
  53.             int u = q[h++];
  54.             de[++dd] = u;
  55.             for(int e = head[u]; e != 0; e = next[e]){
  56.                 int v = to[e];
  57.                 if(v != bgb[u]){
  58.                     bgb[v] = u;
  59.                     q[t++] = v;
  60.                 }
  61.             }
  62.         }
  63.  
  64.         ll[][] dp = new ll[n + 1][];
  65.         int[] sz = new int[n + 1];
  66.  
  67.         for(int id = n; id >= 1; id--){
  68.             int u = de[id];
  69.             sz[u] = 1;
  70.             dp[u] = new ll[2];
  71.             dp[u][0] = 0;
  72.             dp[u][1] = a[u];
  73.  
  74.             for(int e = head[u]; e != 0; e = next[e]){
  75.                 int v = to[e];
  76.                 if(v == bgb[u]) continue;
  77.  
  78.                 int lu = Math.Min(k, sz[u]);
  79.                 int lv = Math.Min(k, sz[v]);
  80.                 int ns = Math.Min(k, sz[u] + sz[v]);
  81.  
  82.                 ll[] ndp = new ll[ns + 1];
  83.                 for(int i = 0; i <= ns; i++) ndp[i] = -1000000000000000000L;
  84.  
  85.                 ll w = we[e];
  86.  
  87.                 for(int i = 0; i <= lu; i++){
  88.                     if(dp[u][i] <= -500000000000000000L) continue;
  89.                     for(int j = 0; j <= lv; j++){
  90.                         if(i + j > k) break;
  91.                         if(dp[v][j] <= -500000000000000000L) continue;
  92.  
  93.                         ll c = dp[u][i] + dp[v][j];
  94.                         if(j > 0 && j < k) c -= w;
  95.  
  96.                         if(c > ndp[i + j]) ndp[i + j] = c;
  97.                     }
  98.                 }
  99.                 dp[u] = ndp;
  100.                 sz[u] = ns;
  101.             }
  102.         }
  103.  
  104.         uiia.coutl(dp[1][k]);
  105.     }
  106.  
  107.     static void LOVE(string s)
  108.     {
  109.         if(File.Exists(s + ".inp"))
  110.         {
  111.             uiia.r = new FileStream(s + ".inp", FileMode.Open, FileAccess.Read);
  112.             uiia.w = new StreamWriter(new FileStream(s + ".out", FileMode.Create, FileAccess.Write), System.Text.Encoding.ASCII, 65536);
  113.         }
  114.         else if(File.Exists("input.txt"))
  115.         {
  116.             uiia.r = new FileStream("input.txt", FileMode.Open, FileAccess.Read);
  117.         }
  118.     }
  119.  
  120.     static void Main()
  121.     {
  122.         uiia.init();
  123.         LOVE("HIV à?");
  124.         int t = 1;
  125.  
  126.         while(t-- > 0) uia();
  127.         uiia.flush();
  128.     }
  129. }
  130.  
  131. public static class uiia
  132. {
  133.     public static Stream r; public static StreamWriter w;
  134.     static byte[] buf = new byte[65536]; static int id = 0, cnt = 0;
  135.     public static void init() { r = Console.OpenStandardInput(); w = new StreamWriter(Console.OpenStandardOutput(), System.Text.Encoding.ASCII, 65536); }
  136.     static int Read() { if(id >= cnt) { id = 0; cnt = r.Read(buf, 0, 65536); if(cnt == 0) return -1; } return buf[id++]; }
  137.     public static string next() {
  138.         int c = Read(); while(c <= 32) { if(c == -1) return null; c = Read(); }
  139.         var sb = new System.Text.StringBuilder();
  140.         while(c > 32) { sb.Append((char)c); c = Read(); }
  141.         return sb.ToString();
  142.     }
  143.     public static int cin() =>(int)nl();
  144.     public static ll nl() {
  145.         int c = Read(); while(c <= 32) { if(c == -1) return 0; c = Read(); }
  146.         bool neg = false; if(c == '-') { neg = true; c = Read(); }
  147.         ll res = 0; while(c > 32) { res = res * 10 + c - '0'; c = Read(); }
  148.         return neg ? -res : res;
  149.     }
  150.     public static void cout(object o) => w.Write(o);
  151.     public static void coutl(object o) => w.WriteLine(o);
  152.     public static void flush() => w.Flush();
  153. }
  154.  
Success #stdin #stdout 0.04s 23316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/X5qUn9
language:
C# (NET 6.0)
created:
1 day ago
visibility:
public

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!