Untitled

 avatar
unknown
plain_text
4 years ago
3.4 kB
4
Indexable
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define ull unsigned long long
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
 
using namespace std;
 
#define pper(a) cerr << #a << " = " << a << endl;
 
void per() { cerr << endl; }
template<typename Head, typename... Tail> void per(Head H, Tail... T) { cerr << H << ' '; per(T...); }
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
 
template<class U, class V> 
ostream& operator<<(ostream& out, const pair<U, V>& a) {
  return out << "(" << a.x << ", " << a.y << ")";
}
 
template<class U, class V> 
istream& operator>>(istream& in, pair<U, V>& a) {
  return in >> a.x >> a.y;
}
 
template<typename W, typename T = typename enable_if<!is_same<W, string>::value, typename W::value_type>::type>
ostream& operator<<(ostream& out, const W& v) { out << "{ "; for (const auto& x : v) out << x << ", "; return out << '}'; }
 
template<class T>
void readArr(T from, T to) {
  for (auto i = from; i != to; ++i) cin >> *i;
}
 
mt19937 mrand(1337); 
unsigned int myRand32() {
  return mrand() & (unsigned int)(-1);
}
 
unsigned ll myRand64() {
  return ((ull)myRand32() << 32) ^ myRand32();
}
 
const int mod = 1000000007;
 
void add(int& a, int b) {
  a += b; if (a >= mod) a -= mod;
}
 
void dec(int &a, int b) {
  a -= b; if (a < 0) a += mod;
}
 
int mult(int a, int b) {
  return a * (ll)b % mod;
}
 
int bp(int a, int b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = mult(res, a);
    a = mult(a, a);
    b >>= 1;
  }
  return res;
}
vector<int> v;
vector<vector<int> > gr;

vector<int> kek;
int dfs(int vertex, int last, int need, int color) {

  //per(vertex, last, need, color, v[vertex]);

  if (vertex == need) {
    if (v[vertex] == color) kek.pb(vertex);
    return 1;
  }

  for (auto to : gr[vertex]) {
    if (to == last) continue;
    if (dfs(to, vertex, need, color)) {
      if (v[vertex] == color) {
        kek.pb(vertex);
      }
      return 1;
    }
  }

  return 0;

}

int f[17][17];

int main(){
#ifdef LOCAL
  freopen("A_input.txt", "r", stdin);
  //freopen("A_output.txt", "w", stdout);
#endif
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n, q;
  cin >> n >> q;

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) f[i][j] = 1e9;
    f[i][i] = 0;
  }

  v.assign(n, -1);
  for (auto &x : v) {
    cin >> x;
    --x;
  }

  gr.assign(n, {});
  for (int i = 0; i < n - 1; ++i) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    gr[a].pb(b);
    gr[b].pb(a);
    f[a][b] = 1;
    f[b][a] = 1;
  }

  for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
      }
    }
  }

  for (int i = 0; i < q; ++i) {
    char t;
    cin >> t;
    if (t == 'U') {
      int a, b;
      cin >> a >> b;
      v[a - 1] = b - 1;
    }
    else {
      int a, b, c;
      cin >> a >> b >> c;
      a--, b--, c--;
      kek.clear();
      dfs(a, -1, b, c);

      if (kek.size() <= 1) {
        cout << "-1\n";
      }
      else {
        int R = 1e9;
        for (int i = 1; i < kek.size(); ++i) {
          R = min(R, f[kek[i]][kek[i - 1]]);
        }
        cout << R << '\n';
      }

    }
  }

}
Editor is loading...