Solution Notes (Albert Gu): There are many ways to do this problem, some of which are faster than others. One solution uses a technique called heavy-light decomposition. Root the tree arbitrarily. Consider an edge between vertices u and v (let u be the parent of v). Call this edge heavy if the size of the subtree rooted at v is at least half the size of the subtree rooted at u, and light otherwise. Note that each parent has at most one heavy edge to a child, so the heavy edges form a set of chains. We will keep track of each heavy chain separately.
Finally, any path from a vertex to the root has at most log n light edges, because advancing up a light edge at least doubles the size of the subtree. This path also has at most log n heavy chains, since a light edge separates every two heavy chains. This means we can divide this path into log n pieces, so adding grass along a path from a vertex to a root will take O(log n) time by adding it to each light edge and heavy chain on the path. Note that we will need to augment each heavy chain with a structure such as a range tree or BIT (binary indexed tree) because we might need to plant grass on only a prefix of a heavy chain.
To update an arbitrary path, we note the following: Planting 1 grass on each edge along the path from A to B is the same as planting 1 grass on each edge from A to the root, 1 grass on each edge from B to the root, and -2 grass on each edge from LCA(A, B) to the root, where LCA denotes the least common ancestor.
(As a note, the memory limits for this problem were extremely tight --- probably a bit too tight; conserving memory was one of the main problems faced by most competitors).
Here is Mark Gordon's code:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstdio>
using namespace std;
/* Heavy Light Implementation */
#define MAXN 100000
int N; // Number of nodes
/* Node fields. */
int VC[MAXN]; // Vertex chain index
int VPOS[MAXN]; // Vertex chain position
/* Chain fields. */
int CP[MAXN]; // Chain parent (-1 if none)
int CLN[MAXN]; // Number of vertexes in chain.
vector<int> E[MAXN];
pair<int, int> hang(int u, int p) {
int nodes = 1;
pair<int, int> result(0, -1);
for(int i = 0; i < E[u].size(); i++) {
int v = E[u][i];
if(v == p) continue;
pair<int, int> res = hang(v, u);
nodes += res.first;
result = max(result, res);
}
E[u].clear();
if(result.second == -1) result.second = u;
E[result.second].push_back(u);
CP[result.second] = p;
result.first = nodes;
return result;
}
/* Before calling E[i] represents the edges of vertex i. After calling E[i] is
* a list (from root to child) of vertexes in chain i. */
void prep_heavylight() {
hang(0, -1);
for(int i = 0; i < N; i++) {
CLN[i] = E[i].size();
for(int j = 0; j < E[i].size(); j++) {
VC[E[i][j]] = i;
VPOS[E[i][j]] = j;
}
}
}
/* Represents the nodes in the range [lo, hi) of chain. */
struct ChainPart {
ChainPart(int chain, int lo, int hi) : chain(chain), lo(lo), hi(hi) {}
int chain;
int lo; // lo node on the chain.
int hi; // hi node on the chain. hi=CLN[chain] means chain connects to parent
};
/* Returns a list of all the sections of the chains on the path from u to v. */
vector<ChainPart> chain_path(int u, int v) {
vector<pair<int, int> > cu, cv;
for(; u != -1; u = CP[VC[u]]) cu.push_back(make_pair(VC[u], VPOS[u]));
for(; v != -1; v = CP[VC[v]]) cv.push_back(make_pair(VC[v], VPOS[v]));
reverse(cu.begin(), cu.end());
reverse(cv.begin(), cv.end());
if(cv.size() < cu.size()) cu.swap(cv);
int i;
for(i = 0; i < cu.size() && cu[i] == cv[i]; i++);
vector<ChainPart> ret;
if(i == cu.size()) {
ret.push_back(
ChainPart(cu.back().first, cu.back().second, cu.back().second));
} else if(cu[i].first == cv[i].first) {
ret.push_back(ChainPart(cu[i].first,
min(cu[i].second, cv[i].second),
max(cu[i].second, cv[i].second)));
++i;
}
for(int j = i; j < cu.size(); j++) {
ret.push_back(ChainPart(cu[j].first, cu[j].second, CLN[cu[j].first]));
}
for(int j = i; j < cv.size(); j++) {
ret.push_back(ChainPart(cv[j].first, cv[j].second, CLN[cv[j].first]));
}
return ret;
}
/* Get rid of empty chain parts. */
vector<ChainPart> filter(const vector<ChainPart>& ch) {
vector<ChainPart> res;
for(int i = 0; i < ch.size(); i++) {
if(ch[i].lo != ch[i].hi) {
res.push_back(ch[i]);
}
}
return res;
}
vector<int> bit[MAXN];
void bit_add(vector<int>& A, int x, int v) {
for(int i = x | A.size(); i < (A.size() << 1); i += i & -i) {
A[i ^ A.size()] += v;
}
}
int bit_get(vector<int>& A, int x) {
int ret = A[0];
for(int i = x; i; i &= i - 1) ret += A[i];
return ret;
}
int main() {
freopen("grassplant.in", "r", stdin);
freopen("grassplant.out", "w", stdout);
int M;
scanf("%d%d", &N, &M);
for(int i = 1; i < N; i++) {
int u, v; scanf("%d%d", &u, &v); u--; v--;
E[u].push_back(v);
E[v].push_back(u);
}
prep_heavylight();
for(int i = 0; i < N; i++) {
if(!CLN[i]) continue;
bit[i] = vector<int>(1 << (32 - __builtin_clz(CLN[i] - 1)), 0);
}
for(int i = 0; i < M; i++) {
char op[2]; int u, v; scanf("%1s%d%d", op, &u, &v); u--; v--;
vector<ChainPart> ch = filter(chain_path(u, v));
if(op[0] == 'P') {
for(int i = 0; i < ch.size(); i++) {
bit_add(bit[ch[i].chain], ch[i].lo, 1);
if(ch[i].hi < CLN[ch[i].chain]) {
bit_add(bit[ch[i].chain], ch[i].hi, -1);
}
}
} else {
assert(ch.size() == 1 && ch[0].lo + 1 == ch[0].hi);
printf("%d\n", bit_get(bit[ch[0].chain], ch[0].lo));
}
}
}