Untitled
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...