Submission #3063391

---

Source Code Expand

// package other2015.utpc2014;

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

public class Main {
    static long __startTime = System.currentTimeMillis();

    static Vertex[] graph;

    static void dfs(Vertex v, Vertex p) {
        v.count = 1;
        v.parent = p == null ? -1 : p.idx;
        for (Edge e : v.adj) {
            int to = e.u + e.v - v.idx;
            if (p != null && to == p.idx) {
                continue;
            }
            dfs(graph[to], v);
            v.count += graph[to].count;
        }
    }

    static List<Edge> tmpedges;

    static void dfsFrom(Vertex v, Vertex p) {
        for (Edge e : v.adj) {
            int to = e.u + e.v - v.idx;
            if (p != null && to == p.idx) {
                continue;
            }
            tmpedges.add(masterEdges[e.idx]);
            dfsFrom(graph[to], v);
        }
    }

    static class Group {
        TreeSet<Edge> edges;
        int root;


        public Group(List<Edge> e, int r) {
            edges = new TreeSet<>(e);
            root = r;
            dfs(graph[root], null);
        }


        public void operate(int e, int s, int d) {
            Edge ed = edges.ceiling(new Edge(e, -1, -1, s));
            edges.remove(ed);
            ed.strength += d;
            edges.add(ed);
        }


        public int[] cutmin() {
            Edge min = edges.first();
            edges.remove(min);

            Vertex newRoot = graph[min.u].parent == min.v ? graph[min.u] : graph[min.v];
            Vertex newRootParent = graph[newRoot.parent];

            Edge mine = new Edge(min.idx, -1, -1, 0);
            newRoot.adj.remove(mine);
            newRootParent.adj.remove(mine);
            
            tmpedges = new ArrayList<>();
            if (graph[root].count < newRoot.count * 2) {
                dfsFrom(graph[root], null);
                for (Edge e : tmpedges) {
                    edges.remove(e);
                }
                int newSmallRoot = root;
                root = newRoot.idx;
                return new int[]{newSmallRoot, min.idx};
            } else {
                dfsFrom(newRoot, null);
                for (Edge e : tmpedges) {
                    edges.remove(e);
                }
                return new int[]{newRoot.idx, min.idx};
            }
        }
    }

    static class Vertex {
        TreeSet<Edge> adj;
        int idx;
        int parent;
        int count;

        public Vertex(int id) {
            idx = id;
            adj = new TreeSet<>();
            parent = -1;
            count = 0;
        }
    }


    static class Edge implements Comparable<Edge> {
        int idx;
        int u;
        int v;
        int strength;

        public Edge(int i, int a, int b, int c) {
            idx = i;
            u = a;
            v = b;
            strength = c;
        }

        @Override
        public int compareTo(Edge o) {
            return strength == o.strength ? idx - o.idx : strength - o.strength;
        }
    }

    static Edge[] masterEdges;

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();


        int[] edgeId = new int[n-1];
        int[] str = new int[n-1];
        List<Edge> edges = new ArrayList<>();
        List<Group> g = new ArrayList<>();
        masterEdges = new Edge[n-1];
        for (int i = 0; i < n-1; i++) {
            Edge e = new Edge(i, in.nextInt()-1, in.nextInt()-1, in.nextInt());
            masterEdges[i] = e;
            edges.add(e);
            str[i] = e.strength;
        }
        graph = new Vertex[n];
        for (int i = 0; i < n ; i++) {
            graph[i] = new Vertex(i);
        }
        for (Edge e : edges) {
            Edge we = new Edge(e.idx, e.u, e.v, 0);
            graph[e.u].adj.add(we);
            graph[e.v].adj.add(we);
        }


        g.add(new Group(edges, 0));

        int q = in.nextInt();
        while (--q >= 0) {
            int type = in.nextInt();
            int e = in.nextInt()-1;
            int gid = edgeId[e];
            if (type == 1) {
                int d = in.nextInt();
                if (gid == -1) {
                    continue;
                }
                g.get(gid).operate(e, str[e], d);
                str[e] += d;
            } else {
                if (gid == -1) {
                    out.println(-1);
                } else {
                    int[] pair = g.get(gid).cutmin();
                    edgeId[pair[1]] = -1;

                    int ngid = g.size();
                    for (Edge ed : tmpedges) {
                        edgeId[ed.idx] = ngid;
                        ed.strength = str[ed.idx];
                    }
                    g.add(new Group(tmpedges, pair[0]));
                    out.println(pair[1]+1);
                }
            }
        }
        out.flush();
    }

    private static void printTime(String label) {
        debug(label, System.currentTimeMillis() - __startTime);
    }

    public static void debug(Object... o) {
        System.err.println(Arrays.deepToString(o));
    }

    public static class InputReader {
        private static final int BUFFER_LENGTH = 1 << 12;
        private InputStream stream;
        private byte[] buf = new byte[BUFFER_LENGTH];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        private int next() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public char nextChar() {
            return (char) skipWhileSpace();
        }

        public String nextToken() {
            int c = skipWhileSpace();
            StringBuilder res = new StringBuilder();
            do {
                res.append((char) c);
                c = next();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public long nextLong() {
            int c = skipWhileSpace();
            long sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = next();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public double nextDouble() {
            return Double.valueOf(nextToken());
        }

        int skipWhileSpace() {
            int c = next();
            while (isSpaceChar(c)) {
                c = next();
            }
            return c;
        }

        boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
    }
}

Submission Info

Judge Result