Codeforces Round #359 (Div. 2) - D. Kay and Snowflake

Problem Statement:
http://codeforces.com/contest/686/problem/D

Summary:
Given a tree of size n <= 300000, answer q <= 300000 queries of the form: find the centroid of subtree v. Centroid of subtree T is defined as a node in T such that when removed the resulting set of disjoint trees have sizes at most |T|/2 (half the size of initial subtree).

Codeforces 538E - Demiurges Play Again

Problem Statement:
538E - Demiurges Play Again

Solution:

Interesting problem. Although it seems to have large search space, by making use of interesting observations we can solve it in linear time (i.e. visiting each node exactly once).

First focus on trying to get the maximum result. Note that both player play optimally, hence the result of a game is deterministic. Consider a subtree T rooted at v. Let v.size be the number of leaves in T. Furthermore, let v.best be the maximum result obtained by an optimal labelling of leaves of T using label i = 1 .. v.size. We have two cases:
1. First player makes a move at node v. He will then choose a child of v that maximises result. For all w children of v, we check w.size and w.best. Pick the one that gives maximum of v.size - w.size + w.best (i.e. we place the biggest labels on the leaves of subtree rooted at w)
2. Second player makes a move at node v. He will choose a child w that minimises the result. Our job is to make the minimum choice as large as possible. It can be proved that the biggest possible will be \(1 + \sum_{w \text{ child of } v} (w.best - 1) \).

Codeforces Rockethon 2015 Problem D1/D2 - Constrained Tree

Problem Statement:
513D2 - Constrained Tree

Solution:
Can a problem be interesting and yet frustrating? The answer turns out to be a loud and painful Yes.. Spent 8 hours just to get this right :/

Btw the editorial to this problem is sufficiently comprehensible hence I would suggest you to read the official editorial instead of this one if you haven't done so. Otherwise, you might benefit from this :)

You are supposed to construct a tree out of a given set of relationships between the nodes on the tree, such that the pre-order and in-order labelling of the nodes agree on each other. That is a pretty confusing semantic in my opinion. And they have recursive definition.

Codeforces Round 285 (Div. 2 C or Div. 1 A) - Misha and Forest

Problem Statement:
501C - Misha and Forest

Solution:
An interesting mix of tree structure and linear algebra. Since we are given the pair \((\text{degree}_v, s_v)\) for each v, we can approach it in an intuitive manner:
1. We will maintain a graph G with vertices v but with no edges just yet. So initially all vertices in G has no neighbouring vertices.
2. Iteratively, we would like to find a vertex v such that the difference between the number of neighbours it currently has and \(\text{degree}_v\) is at most 1. This means that v is short of one vertex. Furthermore, this means that we can determine what vertex is that exactly in O(M) where M is the number of adjacent vertices v currently has, as follows:

Codeforces 455C - Civilization

Problem Statement:
455C - Civilization

Solution:
An nice problem, but my implementation is a bit messy :P

The most important observation that greatly simplify the problem:
If node u has the property such that for every v reachable from u, \(max_{v \text{ reachable from } u} \{ d(u,v) \} \) is minimum, then u must be on the longest path in that connected component. Furthermore, u must be on the middle of that path.

Firstly, why do we want to find such node u? We can think a node with that kind of property as the "midpoint" or "center" of the whole tree, where d(u,v) will be analogous to the "radius" of the tree. So when we have to merge to connected component, all we need to do is to connect the two "centers" of the connected components, and it is guaranteed that the resulting connected component will have the minimum longest path possible.

Codeforces Round: Goodbye 2014

A really nice set of problems :) Well done for the problem setters!
Have just solved problem A to E, loved them so far. Haven't tried F and G yet.

EDIT: just found out that the official tutorial has been released, and it looks really good!

Problem A 
Problem Statement:
500A - New Year Transportation

Solution:
Wow, a pretty intimidating problem A!

The idea is very straight forward, since \(a_i\) is actually a representation of a directed edge connecting vertex \(i\) with \(i+a_i\). Simply run a DFS from node 1 and return YES if we reached the destination node.

Codeforces Round 270 Problem D - Design Tutorial: Inverse The Problem

Problem Statement:
472D - Design Tutorial: Inverse The Problem

Solution:
Pretty interesting problem. Given a matrix of distances between nodes dist[u][v], return a weighted tree that satisfies this matrix. Here is my approach (I believe this is not the most efficient (or even efficient) or clever idea, but it worked :P)

SPOJ - Three-coloring of Binary Trees (THREECOL)

Problem Statement:
SPOJ - THREECOL

Summary:
Given a binary tree as specified (may not be balanced nor complete),  we can color the tree with three colors: red, green and blue, with the following restrictions:
1. A node and its child cannot have the same color.
2. For nodes with two children, the node and its children must all have different colors.
Find the maximum and minimum number possible of nodes colored in green.