KUPC2014 : F - テレパシー

なんか最近SRMでこれ系の問題が多かったのですんなり解けた。
http://kupc2014.contest.atcoder.jp/tasks/kupc2014_f

問題

デカルト座標上にN個の頂点があり、その座標(x[i],y[i])が与えられる。
また、それらは(N-1)本の辺により全域木を成している。

各頂点は力p[i]を持つものとする。
点a,bをつなぐ距離Dの辺が有効であるためには、p[a]+p[b]>=Dでなければならない。

ここで全部の辺を有効にしたいが、p[i]が小さくて有効の条件を満たせない場合がある。
各頂点のp[i]は、コストをc[i]払うことで1だけ増加できる。
各頂点のp[i]の初期値d[i]が与えられたとき、全部の辺を有効にする最小コストを答えよ。

解法

各辺についてp[a]が決まると、p[b]>=D-p[a]と下限が決まる。
この事実をもとに木DPを行っている。

x,yの値の制限より、今見ている点xにおけるp[x]は最大でも2000√2あればよいので、p[x]を0～2000√2程度まで総当たりしていく。

まず、点xの力をp[x]にするにはmax(0,p[x]-d[x])*c[x]のコストがかかる。
また、点xの力がp[x]の時、xに隣接する未到達点yにおいてはp[y]>=D-p[x]でなければならない。
よってDFSによりp[y]>=D-p[x]におけるyのサブツリーのコストの和を取っていくけばよい。

int N;
int X[1001],Y[1001];
int D[1001],C[1001];
vector<pair<int,int> > E[1001];

ll memo[1001][4002];

void dfs(int cur,int pre) {
	int i,j;
	
	ITR(it,E[cur]) {
		int tar=it->first;
		if(tar!=pre) dfs(tar,cur);
	}
	
	memo[cur][4001]=1LL<<60;
	for(j=4000;j>=0;j--) {
		memo[cur][j]=max(0,j-D[cur])*C[cur];
		ITR(it,E[cur]) {
			int tar=it->first;
			if(tar!=pre) memo[cur][j]+=memo[tar][max(0,it->second-j)];
		}
		memo[cur][j]=min(memo[cur][j],memo[cur][j+1]);
	}
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	FOR(i,N) cin>>D[i]>>C[i];
	FOR(i,N-1) {
		cin>>x>>y;
		x--;y--;
		j=(X[x]-X[y])*(X[x]-X[y])+(Y[x]-Y[y])*(Y[x]-Y[y]);
		k=0;
		while(k*k<j) k++;
		E[x].push_back(make_pair(y,k));
		E[y].push_back(make_pair(x,k));
	}
	MINUS(memo);
	dfs(0,-1);
	_P("%lld\n",memo[0][0]);
}

まとめ

一見フローかと思ったけど違った。
辺に対し条件がある場合は、片方の点の状態が定まるともう片方も定まる場合が多いので、DFSが有効。