Codeforces 444 (#254 Div1) E. DZY Loves Planting

問題

辺に重みのついた無向木が与えられる。
二つの頂点u, vについてg(u, v) = uからvへの最短パス上に含まれる辺の重みの最大値
と定義する。

数列p1, p2, p3, .. pn(1≦p1≦n)に対してf(p1, p2, ..., pn)を次のように定める。
f(p1, p2, ..., pn) = min{ g(i, pi) | 1≦i≦n}

pの中に頂点iが出現してよい回数が頂点ごとにx[i]回以下と決まっているとき、
f(p1, p2, ..., pn)の最大値を求めよ。

制約条件

n≦3000
重みは10000以下の正整数
1≦x[i]

方針

二分探索 + union-find + フロー（+ 平方分割）

f(p)をL以上にできるかを二分探索する。
f(p)がL以上であるとき、L未満の辺だけでつながっている頂点間はペアにすることができない。
すなわち、L未満の辺でつながっている部分を縮約して一つの頂点とみなして、
異なる頂点同士で割り当てができるかを見てやればよい。

割り当てができるかは、実はx[i]≧1という条件から一番大きいものを見るだけでgreedyにできるのであるが、フローを使ってもできる。
頂点を倍化して、s側とt側にして、マッチしうるところ（この場合は自分以外）を辺で結んで、容量nのフローが流れるかを見ればよい。

フローのグラフのサイズが相当でかくなりそうなのに、1200msくらいで通ってしまう。
（最悪1000万辺くらい？）

グラフの辺の本数を抑える工夫として、平方分割を考えることができて、これだと70msくらいで通る。
どうするかというと、縮約後の各頂点をB個ごとに分割して、
B個の同じバケット内ではナイーブにマッチングできるところの辺を張る、
異なるバケット間は必ずマッチングできるので、
バケットの代表点を代表ごと、s側t側に両方作り（これをX, Yと呼ぶ）、
s側バケット内の点すべてからXへ容量無限の辺を張り、
Yからt側バケット内の点すべてへ容量無限の辺を張り、
異なるバケットのXからYに容量無限の辺を張る、とする。

ソースコード

int n, x[3000];
vector<pair<int, pi> > es;

int p[3000], src[3000], dst[3000];

int root(int x){
	if(x == p[x]) return x;
	return p[x] = root(p[x]);
}
void merge(int a, int b){
	a = root(a); b = root(b);
	if(a != b){
		p[b] = a;
		src[a] += src[b];
		dst[a] += dst[b];
	}
}
struct flowGraph{
	struct edge{ int to, cap, rev; };
	
	int n, *level, *iter;
	vector<vector<edge> > G;
	
	flowGraph(int sz) : n(sz){
		G.resize(n);
		iter = new int[n]; level = new int[n];
	}
	~flowGraph(){
		delete iter; delete level;
	}
	
	void add(int s, int t, int cap){
		G[s].pb((edge){t, cap, G[t].size()});
		G[t].pb((edge){s, 0, G[s].size() - 1});
	}
	void bfs(int s){
		rep(i, n) level[i] = -1;
		queue<int> q;
		level[s] = 0;
		q.push(s);
		while(!q.empty()){	
			int v = q.front();
			q.pop();
			rep(i, G[v].size()){
				edge &e = G[v][i];
				if(e.cap > 0 && level[e.to] < 0){
					level[e.to] = level[v] + 1;
					q.push(e.to);
				}
			}
		}
	}
	int dfs(int v, int t, int f){
		if(v == t) return f;
		for(int &i = iter[v]; i < (int)G[v].size(); i++){
			edge &e = G[v][i];
			if(e.cap > 0 && level[v] < level[e.to]){
				int d = dfs(e.to, t, min(f, e.cap));
				if(d > 0){
					e.cap -= d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	int max_flow(int s, int t){
		int flow = 0;
		while(1){
			bfs(s);
			if(level[t] < 0) return flow;
			rep(i, n) iter[i] = 0;
			int f;
			while((f = dfs(s, t, inf)) > 0) flow += f;
		}
	}
};

bool check(int mid){
	rep(i, n) p[i] = i, src[i] = 1, dst[i] = x[i];
	rep(i, es.size()){
		if(es[i].first >= mid) break;
		merge(es[i].second.first, es[i].second.second);
	}
	set<int> used;
	vi rs;
	
	rep(i, n){
		int r = root(i);
		if(used.count(r)) continue;
		used.insert(r);
		rs.pb(r);
	}
	
	#if 0
	int s = 2 * rs.size(), t = 2 * rs.size() + 1;
	flowGraph g(t + 1);
	
	rep(i, rs.size()){
		rep(j, i){
			g.add(i, j + rs.size(), inf);
			g.add(j, i + rs.size(), inf);
		}
		g.add(s, i, src[rs[i]]);
		g.add(i + rs.size(), t, dst[rs[i]]);
	}
	return g.max_flow(s, t) >= n;
	
	#endif
	
	#if 1
	int bkt_num = max(1, (int)sqrt(rs.size()));
	int bkt_sz = (rs.size() + bkt_num - 1) / bkt_num;
	int s = 2 * (rs.size() + bkt_num), t = s + 1;
	
	flowGraph g(t + 1);
	rep(i, bkt_num){
		rep(j, bkt_sz){
			int idx = i * bkt_sz + j;
			if(idx >= rs.size()) break;
			
			g.add(s, idx, src[rs[idx]]);
			g.add(idx, 2 * rs.size() + i, inf);
			g.add(idx + rs.size(), t, dst[rs[idx]]);
			g.add(2 * rs.size() + bkt_num + i, idx + rs.size(), inf);
			
			rep(k, j){
				int jdx = i * bkt_sz + k;
				g.add(idx, jdx + rs.size(), inf);
				g.add(jdx, idx + rs.size(), inf);
			}
		}
		rep(j, i){
			g.add(i + 2 * rs.size(), j + 2 * rs.size() + bkt_num, inf);
			g.add(j + 2 * rs.size(), i + 2 * rs.size() + bkt_num, inf);
		}
	}
	return g.max_flow(s, t) >= n;
	#endif
}

int main(){
	cin >> n;
	rep(i, n - 1){
		int a, b, c;
		cin >> a >> b >> c;
		es.pb(mp(c, mp(a - 1, b - 1)));
	}
	rep(i, n) cin >> x[i];
	sort(all(es));
	
	int lo = 0, hi = 10001, mid;
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		
		if(check(mid)) lo = mid;
		else hi = mid;
	}
	cout << lo << endl;
	return 0;
}