import java.io.*; import java.util.*; import java.awt.geom.*; /** * Solution to It Takes a Village * * We'll solve this problem in three steps. * * 1) First, we'll collapse all of cycles down into a single node each. * That will leave us with a graph without cycles: in other words, a tree. * * 2) Next, we'll assign node numbers to the tree such that all of the nodes * in any subtree are contiguous. This will flatten the tree down to an array, * with all subtrees being contiguous intervals. * * 3) Lastly, we'll build a Segment Tree to keep track of the values being put into * our collapsed tree. * * A Segment Tree is a binary tree implemented as an array. Each element of the array represents an interval. * We'll start at 1 instead of 0, for reasons that will soon be obvious. * * Suppose there are n things in the array that we're building a segtree for. * segtree[1] represents the interval [1..n] (or, if you prefer, [0..n-1]. It's the whole enchilada). * From there, if segtree[i] represents the interval [a..b] (a roads = new LinkedList(); // Node of the tree that contains this village public int treenode = -1; // These two will both be used in the DFS // that collapses the cycles. // - onpath signifies that this node is on // the current path from the root in the DFS. // - visited means, well, that the node has been visited in the DFS. public boolean onpath = false, visited = false; /** * Clear all the parameters of a Village. * We'll reuse objects rather than reallocate them, * so this will be done between data sets. */ public void clear() { collapsedto = parent = null; treenode = -1; roads.clear(); onpath = visited = false; } /** * DFS to collapse cycles * * @param from The node we came from in the DFS */ void collapse( Village from ) { // If this village has already been visited, // then we've found a cycle. We've found two different // ways to get to this village. if( visited ) { // We've got to find the highest village in the // traversal tree that is shared above this one. // Call it 'top'. We'll collapse all of the villages // on this cycle to 'top'. Village top = this; // This node was visited on another path. // Trace its parentage until we find // a node on the current path. while( !top.onpath ) top = top.parent; // Traverse this village's parentage, collapsing villages. Village village = this; while( village!=top ) { village.collapsedto = top; village = village.parent; } // Also traverse the current path, collapsing villages. village = from; while( village!=top ) { village.collapsedto = top; village = village.parent; } } else { // We're visited, and we're on the current path. onpath = visited = true; // Remember where we came from. parent = from; // Go to neighbors, EXCEPT who we came from for( Village neighbor : roads ) if( neighbor!=from ) { neighbor.collapse( this ); } // We're returning, so we're no longer on the path. onpath = false; } } /** * DFS to build a tree from the graph of collapsed villages. * * @param from Village we came from in the DFS */ void buildTree( Village from ) { // If we haven't assigned a treenode to this village yet // (it's the equivalent of 'visited') if( treenode<0 ) { // If this village isn't collapsed into another village if( collapsedto==null ) { // Then assign it a new tree node number. treenode = treeindex++; } else { // If this node is collapsed, trace the collapsed // links to the top. That's the tree node that // this village collapses to. Village v; for( v=collapsedto; v.collapsedto!=null; v=v.collapsedto ); treenode = v.treenode; } // DFS to all neighbors for( Village neighbor : roads ) if( neighbor!=from ) { neighbor.buildTree(this); } // Now that we've traversed the entire subtree, // we know the index where it ends. tree[treenode] = treeindex-1; } } } // The Villages! public Village villages[] = new Village[MAX]; // The segment tree that we'll build. public int segtree[] = new int[MAX+MAX+MAX]; /** * * Add a value to the Segment Tree * * @param x The value to add * @param start The start of the interval representing a subtree of the Village tree * @param end The end of the interval representing a subtree of the Village tree * @param index Current index in the Segment tree * @param istart Start of the interval represented by this node in the Segment tree * @param iend End of the interval represented by this node in the Segment tree */ public void addValue( int x, int start, int end, int index, int istart, int iend ) { // If the Village tree interval and the Segment tree interval overlap if( istart<=end && start<=iend ) { // If the Segment tree interval is completely contained within the Village tree interval if( start<=istart && iend<=end) { // We can just drop off the value here and be done with it. // No need to go further down the tree. segtree[index] += x; } else { // Otherwise, go down the tree. Split the Segment tree interval in half. int mid = (istart+iend)/2; // Interval [istart,mid] if( istart<=end && start<=mid ) { addValue( x, start, end, index*2, istart, mid ); } // Interval [mid+1,iend] if( mid+1<=end && start<=iend ) { addValue( x, start, end, index*2+1, mid+1, iend ); } } } } /** * Retrieve a value from the Segment tree * * @param start The index of the Village tree node that we're interested in * @param index Index in the Segment tree * @param istart Start of the interval represented by this node in the Segment tree * @param iend End of the interval represented by this node in the Segment tree * @return Total revenue from this village */ public int getValue( int start, int index, int istart, int iend ) { // We'll sum up the revenue here. int value = 0; // We'll go down the tree, adding up all values // for all intervals that contain 'start' // While the interval is wider than one while( iend>istart ) { // Grab this interval's value value += segtree[index]; // Go left or right, depending on 'start' // It's like a binary search int mid = (istart+iend)/2; if( start<=mid ) { index = index*2; iend = mid; } else { index = index*2+1; istart = mid+1; } } // Add in the current node's value, and be gone. return value+segtree[index]; } /** * Driver. * @throws Exception */ public void doit() throws Exception { sc = new Scanner( System.in ); //new File( "village.sample" ) ); ps = System.out; //new PrintStream( new FileOutputStream( "village.solution" ) ); // Create all villages a priori for( int i=0; i=n ) System.err.println( "PANIC!! Bad k! case " + c ); int x = sc.nextInt(); //if( x<1 || x>1000 ) System.err.println( "PANIC!! Bad x! case " + c ); // Here's the interval representing the subtree rooted here int start = villages[k].treenode; int end = tree[start]; // Add x to the entire interval addValue( x, start, end, 1, 0, n-1 ); } else if( command.equals( "?" )) { int k = sc.nextInt()-1; //if( k<0 || k>=n ) System.err.println( "PANIC!! Bad k! case " + c ); // This one treenode represents this village int start = villages[k].treenode; // Get its sum from the segtree ps.println( getValue( start, 1, 0, n-1 ) ); } else { System.err.println( "PANIC!! Unknown command: " + command ); } } } } /** * @param args */ public static void main( String[] args ) throws Exception { new village_vanb().doit(); } }