func_code_string: #include <bits/stdc++.h>   using namespace std;   const int INF = 1000000005;   struct node {     int l, r, sum, id;   } tr[200010 * 4];   void build(int l, int r, int x) {     tr[x].l = l, tr[x].r = r;     if (l == r) {       tr[x].sum = 0;       tr[x].id = l;       return;     }     int mid = (l + r) >> 1;     build(l, mid, x << 1);     build(mid + 1, r, x << 1 | 1);     if (tr[x << 1].sum > tr[x << 1 | 1].sum)       tr[x].sum = tr[x << 1].sum, tr[x].id = tr[x << 1].id;     else       tr[x].sum = tr[x << 1 | 1].sum, tr[x].id = tr[x << 1 | 1].id;   }   pair<int, int> query(int L, int R, int x) {     int l = tr[x].l, r = tr[x].r;     if (L == tr[x].l && R == tr[x].r) {       return make_pair(tr[x].sum, tr[x].id);     }     int mid = (l + r) >> 1;     if (R <= mid)       return query(L, R, x << 1);     else if (L > mid)       return query(L, R, x << 1 | 1);     else {       pair<int, int> p = query(L, mid, x << 1), q = query(mid + 1, R, x << 1 | 1);       if (p.first > q.first)         return p;       else         return q;     }   }   void upd(int L, int R, int x, int val) {     int l = tr[x].l, r = tr[x].r;     if (L == l && R == r) {       tr[x].sum = val;       tr[x].id = l;       return;     }     int mid = (l + r) >> 1;     if (R <= mid)       upd(L, R, x << 1, val);     else       upd(L, R, x << 1 | 1, val);     if (tr[x << 1].sum > tr[x << 1 | 1].sum)       tr[x].sum = tr[x << 1].sum, tr[x].id = tr[x << 1].id;     else       tr[x].sum = tr[x << 1 | 1].sum, tr[x].id = tr[x << 1 | 1].id;   }   struct EDGE {     int v, next, val;   } edges[200010 * 2];   int head[200010], cnt;   void addedge(int u, int v, int val) {     edges[cnt].v = v;     edges[cnt].next = head[u];     edges[cnt].val = val;     head[u] = cnt++;     edges[cnt].v = u;     edges[cnt].next = head[v];     edges[cnt].val = val;     head[v] = cnt++;   }   int n, m;   int size[200010], fa[200010], dep[200010], son[200010];   void dfs1(int u, int pre, int depth) {     size[u] = 1;     son[u] = -1;     fa[u] = pre;     dep[u] = depth;     for (int i = head[u]; i != -1; i = edges[i].next) {       int x = edges[i].v;       if (x == pre) continue;       dfs1(x, u, depth + 1);       if (son[u] == -1 || size[son[u]] < size[x]) {         son[u] = x;       }       size[u] += size[x];     }   }   int top[200010], pos[200010], no = 1, re[200010];   void dfs2(int u, int tops) {     top[u] = tops;     pos[u] = no++;     if (son[u] == -1) {       return;     }     dfs2(son[u], tops);     for (int i = head[u]; i != -1; i = edges[i].next) {       int x = edges[i].v;       if (x == fa[u] || x == son[u]) continue;       dfs2(x, x);     }   }   void dfs3(int u, int fa) {     for (int i = head[u]; i != -1; i = edges[i].next) {       int x = edges[i].v;       if (x == fa) continue;       upd(pos[x], pos[x], 1, edges[i].val);       dfs3(x, u);     }   }   int sum[200010];   pair<int, int> qry(int x, int y) {     int f1 = top[x], f2 = top[y];     pair<int, int> res(0, -1), tmp;     while (f1 != f2) {       if (dep[f1] < dep[f2]) {         swap(f1, f2);         swap(x, y);       }       tmp = query(pos[f1], pos[x], 1);       if (tmp.first > res.first) res = tmp;       x = fa[f1];       f1 = top[x];     }     if (x == y) return res;     if (dep[x] < dep[y]) swap(x, y);     tmp = query(pos[son[y]], pos[x], 1);     if (tmp.first > res.first) res = tmp;     return res;   }   struct bian {     pair<int, int> z;     long long w, c;     int id;   } ed[200010];   bool cmp(bian a, bian b) {     if (a.w == b.w)       return a.c < b.c;     else       return a.w < b.w;   }   int pa[200010];   bool vis[200010];   int root(int x) {     if (pa[x] == -1)       return x;     else {       pa[x] = root(pa[x]);       return pa[x];     }   }   int main() {     int n, m, i, j;     long long s;     memset(head, -1, sizeof(head));     memset(pa, -1, sizeof(pa));     memset(vis, 0, sizeof(vis));     cnt = 0;     scanf( %d %d , &n, &m);     for (i = 1; i <= m; i++) scanf( %I64d , &ed[i].w), ed[i].id = i;     for (i = 1; i <= m; i++) scanf( %I64d , &ed[i].c);     for (i = 1; i <= m; i++) scanf( %d %d , &ed[i].z.first, &ed[i].z.second);     scanf( %I64d , &s);     sort(ed + 1, ed + m + 1, cmp);     int mn = INF, mnid = -1;     long long ans = 0, sm = 0;     for (i = 1; i <= m; i++) {       int u = ed[i].z.first, v = ed[i].z.second;       if (root(u) != root(v)) {         pa[root(u)] = root(v);         vis[i] = 1;         addedge(u, v, ed[i].w);         if (ed[i].c < mn) mn = ed[i].c, mnid = i;         ans += ed[i].w;       }     }     build(1, n, 1);     dfs1(1, 0, 1);     dfs2(1, 1);     dfs3(1, 0);     for (i = 1; i <= n; i++) re[pos[i]] = i;     int nw = -1, nwf = -1;     ans -= s / mn;     sm = ans + s / mn;     for (i = 1; i <= m; i++) {       if (vis[i]) continue;       pair<int, int> mx = qry(ed[i].z.first, ed[i].z.second);       if (sm - (long long)mx.first + ed[i].w - s / ed[i].c < ans) {         ans = sm - (long long)mx.first + ed[i].w - s / ed[i].c;         nw = i;         nwf = mx.second;       }     }     printf( %I64d n , ans);     if (nw == -1) {       for (i = 1; i <= m; i++) {         if (vis[i] && i != mnid) {           printf( %d %I64d n , ed[i].id, ed[i].w);         } else if (mnid == i && vis[i]) {           printf( %d %I64d n , ed[i].id, ed[i].w - s / ed[i].c);         }       }     } else {       for (i = 1; i <= m; i++) {         if (i == nw) {           printf( %d %I64d n , ed[i].id, ed[i].w - s / ed[i].c);         } else if (vis[i]) {           if (ed[i].z.first == re[nwf] && ed[i].z.second == fa[re[nwf]] ||               ed[i].z.second == re[nwf] && ed[i].z.first == fa[re[nwf]])             continue;           printf( %d %I64d n , ed[i].id, ed[i].w);         }       }     }   }   