Submission #2546023

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e5;
vector<int> g[N];
vector<int> v(N, -1);
int ml[N], mr[N];

int imp = 0;
pair<int, int> dfs(int i, int p, int l, int r) {
  if(v[i] != -1) {
    if((l % 2 + 2) % 2 != v[i] % 2 || (v[i] < l || v[i] > r)) {
      imp = 1;
      cerr << 1 << endl;
      return make_pair(0, 0);
    }
    l = r = v[i];
  }
  int nl = l, nr = r;
  for(int j : g[i]) if(j != p) {
    auto d = dfs(j, i, l - 1, r + 1);
    nl = max(nl, d.first);
    nr = min(nr, d.second);
  }
  if(nl > nr) imp = 1, cerr << 2 << endl;
  ml[i] = nl;
  mr[i] = nr;
  return make_pair(nl - 1, nr + 1);
}

void dfs2(int i, int p, int l) {
  l = max(l, ml[i]);
  if(v[i] == -1) {
    v[i] = l;
  }
  for(int j : g[i]) if(j != p) {
    dfs2(j, i, v[i] - 1);
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n, k; cin >> n;
  for(int i = 0; i < n - 1; i++) {
    int a, b; cin >> a >> b;
    a--; b--;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  int p = -1;
  cin >> k;
  for(int i = 0; i < k; i++) {
    int a, b; cin >> a >> b;
    a--;
    v[a] = b;
  }
  for(int i = 0; i < n; i++) if(v[i] != -1) p = i;
  dfs(p, -1, v[p], v[p]);
  dfs2(p, -1, v[p]);
  if(imp) {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
    for(int i = 0; i < n; i++) {
      cout << v[i] << endl;
    }
  }
}

Submission Info

Judge Result