【校内训练2019-11-10】无聊的日常

【题目概括】

\(n\)个点的树，边权均为\(1\)，求任意一个点\(x\)满足\(M\)条限制。

第\(i\)条限制为“\(x\)到节点\(A_i\)的距离加上\(x\)到节点\(B_i\)的距离不超过\(D_i\)”。

【思路要点】

【代码】

#include <bits/stdc++.h>

#define FI first
#define SE second
#define REP(i, s, t) for (int i = s; i <= t; i++)
#define PER(i, s, t) for (int i = s; i >= t; i--)
#define pb push_back
#define mp make_pair

using namespace std;

template <class T> void chkmax(T& x, T y) { x = max(x, y); }
template <class T> void chkmin(T& x, T y) { x = min(x, y); }

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

inline char gc() {
  static char buf[1 << 25], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 25, stdin), p1 == p2) ? EOF : *p1++;
}

template <class T>
void re(T& x) {
  x = 0; char ch = 0; int f = 1;
  for (; !isdigit(ch); ch = gc()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = gc()) x = x * 10 + ch - 48;
  x *= f;
}

const int N = 1e6 + 5;

int n, m, mx, lim;
vector<int> G[N];
struct Query {
  int u, v, x, w;
} qry[N];
int dep[N][4];

void dfs(int u, int fff, int opt) {
  for (auto v : G[u]) {
    if (v == fff)
      continue;
    dep[v][opt] = dep[u][opt] + 1;
    dfs(v, u, opt);
  }
}

int main() {
  re(n), re(m);
  for (int i = 1; i < n; i++) {
    int u, v; re(u), re(v);
    G[u].pb(v), G[v].pb(u);
  }
  dfs(1, 0, 0);
  for (int i = 1; i <= m; i++) {
    re(qry[i].u), re(qry[i].v), re(qry[i].x);
    qry[i].w = max(0, dep[qry[i].u][0] + dep[qry[i].v][0] - qry[i].x);
    chkmax(mx, qry[i].w);
  }
  for (int i = 1; i <= m; i++)
    if (qry[i].w == mx) {
      dfs(qry[i].u, 0, 1), dfs(qry[i].v, 0, 2);
      lim = qry[i].x;
      break;
    }
  int root = 0;
  for (int i = 1; i <= n; i++)
    if (dep[i][1] + dep[i][2] <= lim && (!root || dep[root][0] > dep[i][0]))
      root = i;
  dfs(root, 0, 3);
  for (int i = 1; i <= m; i++)
    if (dep[qry[i].u][3] + dep[qry[i].v][3] > qry[i].x) {
      printf("NO\n");
      return 0;
    }
  printf("%d\n", root);
  return 0;
}