func_code_string: #include <bits/stdc++.h>   const int N = 1e5 + 10;   int ri() {     char c = getchar();     int x = 0, f = 1;     for (; c <  0  || c >  9 ; c = getchar())       if (c ==  - ) f = -1;     for (; c >=  0  && c <=  9 ; c = getchar()) x = (x << 1) + (x << 3) -  0  + c;     return x * f;   }   struct Pt {     long long x, y;     Pt(long long _x = 0, long long _y = 0) : x(_x), y(_y) {}     Pt operator+(Pt a) { return Pt(x + a.x, y + a.y); }     Pt operator-(Pt a) { return Pt(x - a.x, y - a.y); }     double operator*(Pt a) { return (double)x * a.y - (double)y * a.x; }   } A[N * 60], B[N], p[N], Ans[N * 60];   int tpa, tpb, all, cnt, tot, n, m, sums, G, mn, lst[N], sz[N << 1];   bool del[N << 1];   bool cmp(Pt a, Pt b) { return a.x == b.x ? a.y > b.y : a.x < b.x; }   struct Edge {     int pr[N << 1], to[N << 2], nx[N << 2], tp;     Pt w[N << 2];     Edge() { tp = 1; }     void add(int u, int v, Pt _w) {       to[++tp] = v;       nx[tp] = pr[u];       pr[u] = tp;       w[tp] = _w;     }     void adds(int u, int v, Pt w = Pt()) {       add(u, v, w);       add(v, u, w);     }   } R, T;   void Ins(int u, int v, Pt w) {     ++tot;     T.adds(tot, v, w);     T.adds(tot, lst[u]);     lst[u] = tot;   }   void Build(int u, int fa) {     for (int i = R.pr[u], v; i; i = R.nx[i])       if ((v = R.to[i]) != fa) Ins(u, v, R.w[i]), Build(v, u);   }   void Dfs(int u, int fa, Pt D) {     if (u <= n) p[++cnt] = D;     for (int i = T.pr[u], v; i; i = T.nx[i])       if (!del[i >> 1] && (v = T.to[i]) != fa) Dfs(v, u, D + T.w[i]);   }   void Get(Pt *p, int &cnt, Pt *A, int &tp) {     if (!cnt) return void(tp = 0);     std::sort(p + 1, p + cnt + 1, cmp);     A[tp = 1] = p[1];     for (int i = 2; i <= cnt; ++i)       if (p[i].x != p[i - 1].x) {         for (; tp > 1 && (p[i] - A[tp]) * (A[tp - 1] - A[tp]) >= 0;) --tp;         A[++tp] = p[i];       }   }   void Push() {     if (!tpa) {       for (int i = 1; i <= tpb; ++i) Ans[++all] = B[i];       return;     }     if (!tpb) {       for (int i = 1; i <= tpa; ++i) Ans[++all] = A[i];       return;     }     Ans[++all] = A[1] + B[1];     for (int i = 1, j = 1; i < tpa || j < tpb;) {       ++all;       if (i >= tpa)         Ans[all] = A[i] + B[++j];       else if (j >= tpb)         Ans[all] = A[++i] + B[j];       else {         Pt v1 = A[i + 1] - A[i];         Pt v2 = B[j + 1] - B[j];         Ans[all] = Ans[all - 1] + (v1 * v2 < 0 ? ++i, v1 : (++j, v2));       }     }   }   void Rt(int u, int fa) {     sz[u] = 1;     for (int i = T.pr[u], v; i; i = T.nx[i])       if (!del[i >> 1] && (v = T.to[i]) != fa) {         Rt(v, u);         sz[u] += sz[v];         int tmp = std::max(sz[v], sums - sz[v]);         if (mn > tmp) mn = tmp, G = i;       }   }   void Div(int u, int pres) {     if (pres == 1) return;     sums = pres;     mn = tot + 1;     Rt(u, 0);     del[G >> 1] = true;     int x = T.to[G], y = T.to[G ^ 1], sy = pres - sz[x];     cnt = 0;     Dfs(x, 0, Pt());     Get(p, cnt, A, tpa);     cnt = 0;     Dfs(y, 0, T.w[G]);     Get(p, cnt, B, tpb);     Push();     Div(x, sz[x]);     Div(y, sy);   }   long long F(int p, long long i) { return A[p].x * i + A[p].y; }   int main() {     tot = n = ri();     m = ri();     for (int i = 1; i < n; ++i) {       int u = ri(), v = ri(), a = ri(), b = ri();       R.adds(u, v, Pt(a, b));     }     for (int i = 1; i <= n; ++i) lst[i] = i;     Build(1, 0);     Div(1, tot);     Get(Ans, all, A, tpa);     int r = 1;     long long mmx = 0;     int ps = 0;     for (int i = 1; i <= tpa; ++i)       if (A[i].y > mmx) mmx = A[i].y, ps = i;     for (int i = 0; i < m; ++i) {       for (; r < tpa && F(r + 1, i) >= F(r, i); ++r)         ;       if (!i && mmx != F(r, i)) {         for (int i = 20; i <= 44; ++i) printf( %lld %lld n , A[i].x, A[i].y);         printf( %d %d %d n , r, ps, tot);       }       printf( %lld  , F(r, i));     }     puts(  );     return 0;   }   