ARC063E 木と整数(800) - tekiheiの日記

問題

$N$ 頂点の木が与えられます。各頂点に整数を1つ書き込んで、隣接する頂点に書き込まれている数字の差が $1$ になるようにしたいです。すでに $K$ 個の頂点に数字が書き込まれているとき、条件を満たすように数字を書き込むことができるか判定してください。書き込むことができるならば、例をひとつ構成してください。

制約

$1 \le N \le 10^{5}$
$1 \le K \le N$
$0 \le (書き込まれている数字) \le 10^{6}$

考察

まず、条件を満たすように数字を書き込むことができる必要条件を考えてみます。すでに数字が書き込まれている頂点の集合を $S$ とすると、 $u,v \in S$ に対し、以下が成り立っていなければなりません。

(1) $|num_v-num_u| \le dist(u,v)$
(2) $num_v-num_u \equiv dist(u,v)\ (mod 2)$

一つ辺をたどるごとに数字は多くとも1しか増減しないので、(1)が必要です。また、一つ辺をたどるごとに書かれている数字の偶奇が変わるので、(2)が必要です。

逆にこれらの条件が成り立っていれば、以下の方法で構築することができます。
1. 新たに頂点を1つ作り( $s$ とする)、 $s$ から $v \in S$ にコスト $num_{v}$ の辺を張る
2. $s$ からの最短距離を求める(この最短距離を各頂点に書き込む)

このようにして書き込んだ数が条件を満たしていることを確かめましょう。

$v$ への最短距離が $num_{v}$ と一致していることについて
(1)より $num_{v} \le num_{u}+dist(u,v)$ が成り立つので、 $v$ への最短距離は $num_{v}$ になります。
隣接する頂点の最短距離の差が1になることについて
最短距離の性質より、隣接する頂点の最短距離の差は辺の重み(つまり $1$ )以下です。さらに(2)より、始点 $s$ から隣接する頂点へのパスの長さの偶奇が異なることが分かります¹。よって隣接する頂点への最短距離の差は $1$ になります。

これで、(1)(2)が成り立っているならばこの方法で構築できることが分かりました。また、この方法で構築できなければ(1)または(2)が成り立っていないので、条件を満たす数字の書き込み方は存在しません。よってこの方法で構築してみて、条件を満たしているかどうか確かめることでYesかNoか分かります。²

#include<bits/stdc++.h>
using namespace std;
 
using Graph=vector<vector<int>>;
using P=pair<int,int>;
const int INF=1e9;
 
int main()
{
   int N; cin>>N;
   Graph G(N);
   for(int i=0;i<N-1;i++){
      int a,b; cin>>a>>b;
      a--; b--;
      G[a].push_back(b);
      G[b].push_back(a);
   }
   int K; cin>>K;
   vector<int> num(N,-1);
   for(int i=0;i<K;i++){
      int v,p; cin>>v>>p;
      num[v-1]=p;
   }
 
   vector<int> dist(N,INF);
   priority_queue<P,vector<P>,greater<P>> Q;
   for(int i=0;i<N;i++) if(num[i]>=0){
      dist[i]=num[i];
      Q.push({dist[i],i});
   }
   while(!Q.empty()){
      int v=Q.top().second; Q.pop();
      for(int u:G[v]) if(dist[u]>dist[v]+1){
         dist[u]=dist[v]+1;
         Q.push({dist[u],u});
      }
   }
 
   bool ok=true;
   for(int i=0;i<N;i++){
      if(num[i]>=0 and dist[i]!=num[i]) ok=false;
      for(int j:G[i]) if(dist[i]==dist[j]) ok=false;
   }
   cout<<(ok? "Yes":"No")<<endl;
   if(ok) for(int i=0;i<N;i++) cout<<dist[i]<<endl;
   return 0;
}

まとめ

必要条件を考える
隣接する頂点の最短距離の差は辺の重み以下

感想

必要条件は分かりましたが、そこから進みませんでした。数字の差が $1$ 以下⇒最短距離を書き込めば良さそうと反応できれば良かったと思います。

(2)が成り立っていれば、図のように隣り合う頂点を異なる色で塗りつつ、偶数が書き込まれている頂点が白、奇数が書かれている頂点が黒になるようにできると思います。そうすると始点から白い頂点へのパスの長さは偶数、黒い頂点へのパスの長さは奇数になることが分かります。↩
「解が存在するための必要条件が成り立っているならば構築できる方法」で構築できなければ、(その条件が成り立っていないので)解は存在しないということでしょうか(自問)。↩