UVa 12161: Ironman Race in Treeland

UVaデビューです。

重心分解。問題はどうやってsubtree間のpathを高速に処理するか。
まず各subtreeの重心からのpathについてdamageとlengthの合計を求めておく。
それをすべて一つの配列に入れてsortして、その配列と同じ大きさのsegtreeにソート後のlengthを入れておく。
segtreeは区間のmaxと、ある値のupdateをできるものを用意する。
さらにsubtreeのpathを順番に見ていき、許容されるdamage内でlengthが最大のものをsegtreeから求める。
この時、同じsubtree内のpathを参照するとダメなので、見ているpathに相当するsegtreeの値を0にしておく。

一発でsample合って、これは来たか?と思ったが結局3WA。

POJと違っていつものテンプレート使えるからよろしい。

namespace CD { //centroid decomposition

	struct edge { int to, damage, length; };

	vector<edge> G[MAX_N];
	bool centroid[MAX_N];
	int subtree_size[MAX_N];

	void init(int n) {
		rep(i, 0, n) G[i].clear();
	}
	void add_edge(int a, int b, int d, int c) {
		G[a].push_back((edge){b, d, c});
		G[b].push_back((edge){a, d, c});
	}

	int compute_subtree_size(int v, int p) {
		int c = 1;
		rep(i, 0, (int)G[v].size()) {
			int w = G[v][i].to;
			if(w == p || centroid[w]) continue;
			c += compute_subtree_size(G[v][i].to, v);
		}
		subtree_size[v] = c;
		return c;
	}

	pi search_centroid(int v, int p, int t) { 
		pi res = pi(inf, -1);
		int s = 1, m = 0;
		rep(i, 0, (int)G[v].size()) {
			int w = G[v][i].to;
			if(w == p || centroid[w]) continue;

			MIN(res, search_centroid(w, v, t));

			MAX(m, subtree_size[w]);
			s += subtree_size[w];
		}
		MAX(m, t - s);
		MIN(res, pi(m, v));
		return res;
	}

	void update(int s, int n);

	void solve_subproblem(int v) {
		compute_subtree_size(v, -1);
		int s = search_centroid(v, -1, subtree_size[v]).sec;
		centroid[s] = true;

		int cnt = 0;
		rep(i, 0, (int)G[s].size()) {
			if(centroid[G[s][i].to]) continue;
			solve_subproblem(G[s][i].to);
			cnt++;
		}
		update(s, cnt);
		centroid[s] = false;
	}

	////////////////////////////////////////////// edit from here
	
	//distance from centroid
	void enumerate_pathes(int v, int p, int d, int l, int cnt, vector<ppi> &ds) {
		ds.push_back(make_pair(pi(d, l), cnt));
		rep(i, 0, (int)G[v].size()) {
			int w = G[v][i].to;
			if(w == p || centroid[w]) continue;
			enumerate_pathes(w, v, d + G[v][i].damage, l + G[v][i].length, cnt, ds);
		}
	}

	int fd(const vector<ppi>& v, int n) {
		int lv = -1, rv = (int)v.size();
		while(rv - lv > 1) {
			int m = (lv + rv) / 2;
			if(v[m].fst.fst > n) rv = m;
			else lv = m;
		}
		return rv;
	}

	void update(int s, int n) {
		vector<ppi> ds;
		vector<vector<ppi>> tds(n);
		vector<vi> at(n);

		int cnt = 0;
		rep(i, 0, (int)G[s].size()) {
			if(centroid[G[s][i].to]) continue;
			tds[cnt].push_back(make_pair(pi(0, 0), cnt));
			//debug("omo", G[s][i].damage, G[s][i].length);
			enumerate_pathes(G[s][i].to, s, G[s][i].damage, G[s][i].length, cnt, tds[cnt]);

			ds.insert(ds.end(), tds[cnt].begin(), tds[cnt].end());
			cnt++;
		}
		int m = (int)ds.size();
		segtree seg;

		seg.init(m);
		sort(all(ds));

		rep(i, 0, m) {
			at[ds[i].sec].push_back(i);
			seg.update(i, ds[i].fst.sec);
		}

		//debug(s, ds);
		//seg.show();

		rep(i, 0, n) {
			rep(j, 0, (int)at[i].size()) {
				seg.update(at[i][j], 0);
			}

			rep(j, 0, (int)at[i].size()) {
				ppi pp = ds[at[i][j]];
				pi p = pp.fst;
				int at = fd(ds, M - p.fst);
				int res = seg.get(0, at).v;
				//debug(p.fst, M - p.fst, at, p.sec, res);
				MAX(ans, p.sec + res);
			}
			rep(j, 0, (int)at[i].size()) {
				seg.update(at[i][j], ds[at[i][j]].fst.sec);
			}
		}
	}
}


void solve() {
	cin >> Q;
	rep(q, 1, Q + 1) {
		cin >> N >> M;
		CD::init(N);
		rep(i, 0, N - 1) {
			int a, b, d, c;
			cin >> a >> b >> d >> c; a--; b--;
			CD::add_edge(a, b, d, c);
		}
		ans = 0;
		CD::solve_subproblem(0);
		cout << "Case " << q << ": " << ans << "\n";
	}
}

解いているときふとmap使えそうだなと思ったけど、使い方がよくわからず結局segtreeで解いてしまった。
イテレーターのスマートな使い方とか習得したい。