これもあまり迷わず解けた。
http://njpc2017.contest.atcoder.jp/tasks/njpc2017_e
問題
N頂点(N-1)有向辺のグラフが与えられる。
各辺には距離が与えられている。
このグラフは辺を無向辺とみなすと木を成している。
以下の条件を満たすように辺の向きを変えたい。
最小何本の辺の向きを変える必要があるか。
- ある頂点を1つゴールとして設定する。
- 全辺は各頂点からこのゴールに向かうようにする。
- 全頂点からゴールまでの距離の最大値はD以下である。
解法
各頂点について、最遠点までの距離と、辺のうちその頂点から外向きに向いている辺(=向きを逆にしなければならない辺)の数を数え上げよう。
それぞれDFSを2回行うテクで求められる。
最遠点を求めるのは直径を求める手法でもよい。(結局2回DFS行う点で大差ない)
int N,D; int A[101010],B[101010]; int C[101010]; int rev[101010]; vector<int> dist[101010]; vector<pair<int,int>> E[101010]; int dfs(int cur,int pre) { dist[cur].push_back(0); FORR(r,E[cur]) { int tar=(r.second?A[r.first]:B[r.first]); if(tar!=pre) dist[cur].push_back(dfs(tar,cur)+C[r.first]); } sort(ALL(dist[cur])); reverse(ALL(dist[cur])); return dist[cur][0]; } void dfs2(int cur,int pre,int par) { dist[cur].push_back(par); sort(ALL(dist[cur])); reverse(ALL(dist[cur])); FORR(r,E[cur]) { int tar=(r.second?A[r.first]:B[r.first]); if(tar!=pre) { int id=(dist[cur][0]==dist[tar][0]+C[r.first]); dfs2(tar,cur,dist[cur][id]+C[r.first]); } } } int dfs3(int cur,int pre) { FORR(r,E[cur]) { int tar=(r.second?A[r.first]:B[r.first]); if(tar!=pre) rev[cur]+=dfs3(tar,cur)+(1^r.second); } return rev[cur]; } void dfs4(int cur,int pre,int par) { rev[cur]+=par; FORR(r,E[cur]) { int tar=(r.second?A[r.first]:B[r.first]); if(tar!=pre) { int left=rev[cur]-(rev[tar]+(1^r.second)); dfs4(tar,cur,left+r.second); } } } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>D; FOR(i,N-1) { cin>>A[i]>>B[i]>>C[i]; A[i]--; B[i]--; E[A[i]].push_back({i,0}); E[B[i]].push_back({i,1}); } dfs(0,-1); dfs2(0,-1,0); dfs3(0,-1); dfs4(0,-1,0); int mi=1<<20; FOR(i,N) if(dist[i][0]<=D) mi=min(mi,rev[i]); if(mi==1<<20) mi=-1; cout<<mi<<endl; }
まとめ
下校時は問題ないらしい。