...

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

int main() {
    const string suffix = "@odoo.com";
    string s; cin >> s;

    int last_pos_at = s.find_last_of('@');

    if(s.size() < suffix.size()) {cout << "no\n"; return 0; }
    if(last_pos_at == string::npos) {cout << "no\n"; return 0;}
    if(last_pos_at < 2 || last_pos_at > 4) {cout << "no\n"; return 0;}
    if(s.substr(last_pos_at) != suffix) {cout << "no\n"; return 0; }
    
    for(int i = 0; i < last_pos_at; i++) {
        if(s[i] < 'a' || s[i] > 'z') {cout << "no\n"; return 0; }
    }

    cout << "yes\n";
}

...

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

int main() {
    int T; cin >> T;
    const string odoo = "ODOO";
    while(T--) {
        string s; cin >> s;

        int ans = INT_MAX;
        for(int i = 0; i + 3 < s.size(); ++i) {
            int diff = (
                (s[i] != odoo[0]) + 
                (s[i + 1] != odoo[1]) +
                (s[i + 2] != odoo[2]) +
                (s[i + 3] != odoo[3])
            );
            ans = min(ans, diff);
        }
        cout << ans + s.size() - 4 << "\n";
    }
}

The idea is to sort the modules by position in a decreasing order and the viruses by position in an increasing order.You iterate over the modules, for each module we iterate over the viruses, if they collide (module position <= virus position) and the virus capacity is greater or equal to the module capacity, the module is dead. The virus is also dead, if the capacities are equal else, the module capacity is decreased by the virus capacity (the virus is dead) and continues the path to the server.

from collections import defaultdict

def solve():
    n, m, q = map(int, input().split())
    modules = []
    viruses = []
    virusCapacities = defaultdict(dict)

    for _ in range(n):
        name, capacity, position = input().split()
        modules.append((name, int(capacity), int(position)))

    for _ in range(m):
        id, position = map(int, input().split())
        viruses.append((id, position))

    for _ in range(q):
        virusId, moduleName, capacity = input().split()
        virusCapacities[int(virusId)][moduleName] = int(capacity)

    modules = sorted(modules, key=lambda x: x[2], reverse=True)
    viruses = sorted(viruses, key=lambda x: x[1])

    ans = []

    for moduleName, moduleCapacity, modulePosition in modules:
        passed = True
        for virusId, virusPosition in viruses:
            if virusPosition < modulePosition or moduleName not in virusCapacities.get(virusId, dict()):
                continue
            
            virusCapacity = virusCapacities[virusId][moduleName]
            if moduleCapacity == virusCapacity:
                passed = False
                del virusCapacities[virusId]
                break
            elif moduleCapacity < virusCapacity:
                passed = False  
                break
            else:
                del virusCapacities[virusId]
                moduleCapacity -= virusCapacity

        if passed:
            ans.append(moduleName)

    return ans
   

if __name__ == "__main__":
    a = solve()
    print(len(a))
    print(*a)

It's easy to notice that if a number x of servers can finish the tasks within the time limit $$$x + 1$$$ will be able to do this too, as we want to get the minimum number of servers this becomes a classic problem that we use binary search.

Now we just need to do the validation function of the binary search, in the problem, all the tasks need to be started in order, so we just need to simulate the process of allocating the next task to the server that will be free first. To do this in a fast way we can use a priority queue to help us.

The final complexity will be $$$n * log(n) * log (n)$$$.

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

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << "{"; for (typename vector<T>::const_iterator vi = v.begin(); vi != v.end(); ++vi) { if (vi != v.begin()) os << ", "; os << *vi; } os << "}"; return os; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { os << '(' << p.first << ", " << p.second << ')'; return os; }
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

#define optimize ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl "\n"

#define fi first 
#define se second 
#define pb push_back

#define all(x) x.begin(),x.end()
#define ms(x,a) memset(x,a,sizeof(x))

#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f

#define mod 1000000007LL
#define MAXN 200010

/* -------------------------------- Solution starts below -------------------------------- */

ll N, T;
ll A[MAXN];

bool check(ll m) { 
    
    priority_queue<ll, vector<ll>, greater<ll>> pq;

    for(int i = 0; i < m; i++) {
        pq.push(0);
    }

    for(int i = 0; i < N; i++) {
        ll x = pq.top();
        pq.pop();

        if(x + A[i] > T) return false;

        pq.push(x + A[i]);
    }

    return true;
}

void solve() {

    ll l = 1, r = MAXN;

    while(l < r) {
        ll m = (l + r) / 2;

        if( check(m) )  r = m;
        else            l = m + 1;
    }

    if(l == MAXN) {
        l = -1;
    }

    cout << l << endl;
}

int main() {

	optimize;
	
    cin >> N >> T;

    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }

	solve();
    
	return 0;
}

from queue import PriorityQueue
n, t = map(int, input().split())
a = list(map(int, input().split()))

def ok(u,t, a):
    mx = 0
    pq = PriorityQueue()
    sz = 0
    for i in range(len(a)):
        if sz < u:
            pq.put((a[i]))
            mx = max((mx,a[i]))
            sz += 1
        else:
            x = pq.get()
            x += a[i]
            mx=max((mx,x))
            pq.put(x)
    return mx <= t


if max(a) > t :
    print(-1)
    exit(0)
l = 1
r = n

while l < r:
    md = (l+r)//2
    if(ok(md,t,a)):
        r=md
    else:
        l=md+1
print(l)

We want to calculate the maximum prefix sum for every subarray (prefix can be empty). To calculate prefix sum for just one subarray we start from the begining and loop over the subarray , we incremenet the current sum and we maximise over all sums. We can use this idea to make it more general, if we consider that sum from $$$l$$$ to $$$r$$$ is equal to $$$suff[l]-suff[r+1]$$$ ($$$suff$$$ is the suffix sum of the whole array$. If we fix the $$$l$$$ now , we will only consider $$$r$$$ as variable. Since starting from $$$l$$$ and going right will only increase the prefix sum then the prefix sum sequecnce will be in this form $$$a,a,a,b,b,b,c,c,d,d,d,d..$$$ where $$$a\lt b \lt c \lt d...$$$, since $$$l$$$ is fixed we can convert this sequence into a sequence of $$$rs$$$ then it will look like this $$$suff[l+1]...,suff[r1+1]....,suff[r2+1]...,suff[r3+1]...$$$ where $$$suff[l+1] > suff[r1+1] > suff[r2+1]..$$$ and $$$l \lt r1 \lt r2 ..$$$. So to get the answer we can keep always a sorted stack of the values where we pop from top the values that are greater than the current suffix to keep it always sorted and we update the sum accordingly it depends on in how many positions is the removed/added suffix is the maximum.

// Mtaylor
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define endl '\n';

typedef long long ll;
const int N = 3e5 + 5;

int t;
int n;
ll a[N];
ll sum[N];
vector<int> p;
void test_case() {
    cin >> n;
    p.clear();
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ll s = 0;
    sum[n] = 0;
    p.pb(n);
    ll cur = 0;
    ll ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        s += a[i];
        sum[i] = s;
        while (p.size() && sum[p.back()] > s) {
            int y = p.back();
            p.pop_back();
            int x = -1;
            if (p.size()) {
                x = p.back();
            }
            if (x != -1) {
                cur -= sum[y] * (x - y);
            } else {
                cur -= sum[y] * (n + 1 - y);
            }
        }
        int x = -1;
        if (p.size()) {
            x = p.back();
        }
        if (x != -1) {
            cur += sum[i] * (x - i);
        } else {
            cur += sum[i] * (n + 1 - i);
        }
        p.push_back(i);
        ans -= cur;
        ans += sum[i] * (n - i + 1);
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        test_case();
    }
    return 0;
}

...

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

#define int long long
int n, k, q;
struct segmentTree{
        vector<int> values;
        int sz = 1;
        void init(int n){
                while(sz < n) sz *= 2;
                values.resize(2 * sz, 1);
        }
        void set(int i, int v, int x, int lx, int rx){
                if(rx - lx == 1){
                        values[x] = v % k;
                        return;
                }
                int m = (lx + rx) >> 1;
                if(i < m)
                        set(i, v, 2 * x + 1, lx, m);
                else
                        set(i, v, 2 * x + 2, m, rx);

                values[x] = values[2 * x + 1] * values[2 * x + 2] % k;
        }
        void set(int i, int v){
                set(i, v, 0, 0, sz);
        }

        int ans(int x, int lx, int rx, int ai){
                if (rx - lx == 1){
                        return lx;
                }
                int m = (lx + rx) >> 1;
                if (values[2 * x + 1] * ai % k == 0){
                        return ans(2 * x + 1, lx, m, ai);
                }
                return ans(2 * x + 2, m, rx, ai * values[2 * x + 1] % k);
        }
        int ans(int x){
                if (x % k == 0)
                        return 0;
                if (values[0] * x % k != 0)
                        return -1;
                return ans(0, 0, sz, x);
        }
};

const int N = 2e5 + 10;
vector<int> adj[N];
int ans[N], a[N];
vector<pair<int,int>> updates[N];
segmentTree st;

void dfs(int node, int p){
        for (auto [i, y] : updates[node]){
                st.set(i, y);
        }
        ans[node] = st.ans(a[node]);
        for(int ch : adj[node]){
                if(ch != p)
                        dfs(ch, node);
        }
        for (auto [i, y] : updates[node]){
            st.set(i, 1);
        }
}
int32_t main() {
        cin.tie(0);
        cin.sync_with_stdio(0);

        cin>>n>>k>>q;
        for(int i = 0; i < n; i++){
                cin>>a[i]; a[i] %= k;
        }
        for(int i = 1; i < n; i++){
                int p; cin>>p; --p;
                adj[p].push_back(i);
        }
        for(int i = 1; i <= q; i++){
                int x, y;
                cin>>x>>y;
                updates[x - 1].push_back({i, y});
        }
        st.init(q + 10);
        dfs(0, 0);
        for(int i = 0; i < n; i++){
                cout<<ans[i]<<' ';
        }
}

The problem consists of a tree, where each vertex of this tree contains four pieces of information. The goal is to calculate the maximum profit for all ancestors of a chosen vertex. Let's summarize the problem by considering just one vertex:

For a vertex, let's call it $$$u$$$, we iterate through all ancestors of $$$u$$$ and take its maximum profit considering the equation: $$$profit[v] = pr[v] * d + bonus[v]$$$, for all $$$v$$$ ancestor of $$$u$$$;

This works, but it's not the best solution since we would have to linearly traverse the ancestors, in the worst case, traversing the entire tree in $$$O(n)$$$. If $$$d$$$ were fixed, we could precompute all the answers and retrieve them with binary lifting, but that's not our case since $$$d$$$ is too large. What to do? Well, in this case, we can use a well-known trick for dynamic programming optimization called Convex Hull Trick (aka CHT). The profit equation is identical to the equation of a line with slope $$$pr[v]$$$ and intercept $$$bonus[v]$$$.

Note that, for every child, its "pr" will always be strictly greater than its parent's $$$pr$$$, hence, the slopes of the lines will always be "increasing". This gives us the condition to use the CHT in the simplest possible way. I won't delve into CHT here and how it works; you can check more on this wonderful blog: https://codeforces.me/blog/entry/63823.

Assuming you already know about CHT and have solved many problems with it, we can proceed to the challenge: answering $$$Q$$$ queries.

Note that each path from the root to a leaf $$$x$$$ is entirely independent of another path from the root to a leaf $$$y$$$, which allows us to divide the queries for each of these paths. We'll do this using a depth-first search (DFS). Reading all the queries and answering them in a completely arbitrary way is commonly referred to as "offline" responses. This is convenient in many cases where sorting the queries is better than answering them as they come. Here, our sorting will be according to the visit of each vertex in our DFS.

To do this, for each vertex you visit in the DFS, first add the line of this vertex to your structure that stores the lines of the convex hull. Then answer all the queries for that specific vertex. This will give us a nice complexity of: $$$O(q[u] * log(p[u]))$$$ -> $$$q[u]$$$ = queries for vertex u. -> $$$p[u]$$$ = number of ancestors for vertex u.

But that alone is not enough... Suppose (you need to know the convex hull trick to understand this step) the line of some vertex $$$v$$$ ancestral to $$$u$$$ was removed from our CHT. Upon entering another path that still contains $$$v$$$ how do we re-add it?

You have the question, I have the solution: PERSISTENCE. Well... scholars will say that it's not necessarily persistence because there is a list of properties that need to be followed for a data structure to be considered persistent, but the focus here is for you to somehow store old versions of the CHT so that you can update and revert to these versions without changing the result at all.

And to do this, it's simple. Add a stack to your CHT. Every time we make a removal, we'll store what was the last size of our structure, and we'll just add the new stack to the top of the stack. If a line is not on top of your stack, it means it's not part of the current version of the CHT.

And how to retrieve old versions? git reset --hard Well, just rollback! Go back to the previous size (which you'll store in an array for each change) and pop all elements from the stack that are not part of that version.

This will give us an amortized complexity of O(1) for rollback and O(1) for addition, even if you add more than one line for some rollbacks and additions (this is because a line is added only once and removed only once).

I know, a lot of information. But if you're already familiar with CHT, understanding the rollback part should be easy. You can see a wonderful implementation of a convex hull trick with rollback here: https://github.com/kinhosz/ICPC-Library/blob/main/code/DP/CHTPersistent.cpp. (Please, if you like it, give a like to our repository; it motivates me to produce more programming content, including competitive programming :) ).

Okay, now, with rollback ready and offline queries answered, just print your result in the order of the input. And in the end, you'll have your solution in $$$O(Q * log(N))$$$.

Okay, now I'll throw a challenge at you. If I forced you to answer the queries online and the $$$PR$$$ (profit rate) of a vertex $$$N$$$ was NOT strictly greater than that of its parent, how would you solve it?

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

typedef long long ll;

vector<int> v_pr;
vector<int> v_bonus;
vector<vector<int>> adj;
vector<int> query;
vector<vector<int>> offline;
vector<ll> ans;

class CHTPersistent{
  struct Line{
    ll m;
    ll c;
    Line(){}
    Line(ll _m, ll _c): m(_m), c(_c){}
  };

  vector<vector<Line>> hull;
  int SZ = 0;
  vector<int> version_idx;
  vector<int> version_sz;

  double inter(Line t1, Line t2){
    double ret;
    ret = (double)(t2.c - t1.c)/(t1.m - t2.m);
    return ret;
  }

  void add(Line curr){
    Line temp, temp2;
    version_sz.push_back(SZ);

    if(SZ > 1){
      int s = 0;
      int e = SZ-1;

      while(s < e){
        int p = (s+e)/2;

        temp = hull[p+1].back();
        temp2 = hull[p].back();

        double point = inter(temp, temp2);
        double point2 = inter(temp, curr);

        if(point < point2){
          s = p+1;
        }
        else{
          e = p;
        }
      }
      SZ = s+1;
    }

    if(hull.size() == SZ){
      vector<Line> x;
      hull.push_back(x);
    }

    hull[SZ].push_back(curr);
    version_idx.push_back(SZ);
    SZ++;
  }

public:
  void add(ll m, ll c){
    add(Line(m, c));
  }

  ll query(ll find){
    int s = 0;
    int e = SZ-1;

    while(s < e){
      int p = (s+e)/2;

      double point = inter(hull[p].back(), hull[p+1].back());
      if(point < find){
        s = p+1;
      }
      else{
        e = p;
      }
    }

    ll ret = (hull[s].back().m * find) + hull[s].back().c;
    return ret;
  }

  void rollback(){
    SZ = version_sz.back();
    version_sz.pop_back();
    hull[version_idx.back()].pop_back();
    version_idx.pop_back();
  }

  int size(){
    return SZ;
  }
};

CHTPersistent cht;

void dfs(int u) {
	cht.add(v_pr[u], v_bonus[u]);

	for(int q_id: offline[u]) {
		ll d = query[q_id];
		ans[q_id] = cht.query(d);
	}

	for(auto v: adj[u]) dfs(v);

	cht.rollback();
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

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

	adj.resize(n);
	v_pr.resize(n);
	v_bonus.resize(n);
	offline.resize(n);
	ans.resize(q);
	int root = -1;

	for(int i=0;i<n;i++) {
		int id, pid, pr, bonus;
		cin >> id >> pid >> pr >> bonus;
		id--;
		pid--;
		v_pr[id] = pr;
		v_bonus[id] = bonus;
		if(pid == -1) {
			root = id;
		}
		else {
			adj[pid].push_back(id);
		}
	}

	for(int i=0;i<q;i++) {
		int id, d;
		cin >> id >> d;
		id--;
		query.push_back(d);
		offline[id].push_back(i);
	}

	dfs(root);

	for(int i=0;i<q;i++){
		cout << ans[i] << "\n";
	}
}	

To solve this problem, we will store in segment tree of sets based on the HLD decompositions of the tree for each node the indices of the cycle $$$i$$$ such that the node is in the path between nodes in positions $$$i$$$ and $$$i+1$$$. We can use a data structure to calculate the sum of lengths of paths between every consecutive nodes in the cycle (Fenwick tree is better since it's faster in practice). Now to get the answer , we will first query the hld seg tree to get the first index $$$i$$$ after $$$p$$$ in the cycle such that $$$u$$$ is in the path between $$$p$$$ and $$$p+1$$$. The total sum is then equal to $$$ Rangesum(p,i-1) + dist(v[i],u)$$$ so it represents all the paths to go fully and the last path we only take the distance to reach the node.

// Mtaylor
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define endl '\n';
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

typedef long long ll;
const int N = 1e5 + 5;
const int E = 1e6 + 5;

#define neig(u, v, e, g) \
    for (int e = g.head[u], v; ~e && ((v = g.to[e]), 1); e = g.nxt[e])

class ADJ {
   public:
    int head[E], to[E], nxt[E], n, edgcnt = 0;
    ll cst[E];

    void addEdge(int a, int b, int c = 0) {
        nxt[edgcnt] = head[a];
        head[a] = edgcnt;
        to[edgcnt] = b;
        cst[edgcnt] = c;
        edgcnt++;
    }

    void addBiEdge(int a, int b, int c = 0) {
        addEdge(a, b, c);
        addEdge(b, a, c);
    }
    void init(int _n) {
        n = _n;
        memset(head, -1, n * sizeof(head[0]));
        edgcnt = 0;
    }
} adj;

set<int> tree[4 * N];
int n, k, q;
int v[N];
int t, p, u;
set<int>::iterator it;
int getVal(int id, int k) {
    if (!tree[id].size()) return -1;

    it = tree[id].lower_bound(k);
    if (it != tree[id].end()) {
        return *it;
    }
    return *tree[id].begin();
}

int mrg(int x, int y, int k) {
    if (x == -1 || y == -1) return max(x, y);
    if (x >= k && y >= k) {
        return min(x, y);
    }
    if (x < k && y < k) {
        return min(x, y);
    }
    return max(x, y);
}

int queryPosition(int qp, int k, int id = 0, int ns = 0, int ne = n - 1) {
    int rs = getVal(id, k);
    if (ns == ne) {
        return rs;
    }
    int l = 2 * id + 1;
    int r = l + 1;
    int md = ns + (ne - ns) / 2;
    if (qp <= md) {
        rs = mrg(rs, queryPosition(qp, k, l, ns, md), k);
    } else {
        rs = mrg(rs, queryPosition(qp, k, r, md + 1, ne), k);
    }
    return rs;
}

void updateRange(int qs, int qe, int p, int to_ins, int id = 0, int ns = 0,
                 int ne = n - 1) {
    if (qs > ne || qe < ns) return;
    if (qs <= ns && qe >= ne) {
        if (to_ins) {
            tree[id].insert(p);
        } else {
            tree[id].erase(p);
        }
        return;
    }
    int l = 2 * id + 1;
    int r = l + 1;
    int md = ns + (ne - ns) / 2;
    updateRange(qs, qe, p, to_ins, l, ns, md);
    updateRange(qs, qe, p, to_ins, r, md + 1, ne);
}

class HLD {
   public:
    vector<int> par, sze, dpth, ndToIdx, chHead, heavyChld, idxToNd;
    int n, curPos;
    HLD() {}
    void run(ADJ &adj) {
        n = adj.n;
        curPos = 0;
        par.assign(n, -1);
        sze.assign(n, 0);
        dpth.assign(n, 0);
        ndToIdx.assign(n, 0);
        chHead.assign(n, 0);
        heavyChld.assign(n, 0);
        idxToNd.assign(n, 0);
        calcsz(0, adj);
        HLD_util(0, adj);
    }

    void calcsz(int u, ADJ &adj) {
        heavyChld[u] = -1;
        sze[u] = 1;
        int mx = 0, mxv;
        neig(u, v, e, adj) {
            if (par[u] == v) continue;
            par[v] = u;
            dpth[v] = dpth[u] + 1;
            calcsz(v, adj);
            if (sze[v] > mx) {
                mx = sze[v];
                mxv = v;
            }
            sze[u] += sze[v];
        }
        if (mx * 2 > sze[u]) {
            heavyChld[u] = mxv;
        }
    }

    void HLD_util(int u, ADJ &adj, int c = 0) {
        if (u == -1) return;
        idxToNd[curPos] = u;
        ndToIdx[u] = curPos++;
        chHead[u] = c;
        HLD_util(heavyChld[u], adj, c);
        neig(u, v, e, adj) {
            if (v == par[u]) continue;
            if (v == heavyChld[u]) continue;
            HLD_util(v, adj, v);
        }
    }
    int lca(int u, int v) {
        while (chHead[u] != chHead[v]) {
            if (dpth[chHead[v]] > dpth[chHead[u]]) swap(u, v);
            u = par[chHead[u]];
        }
        if (dpth[u] > dpth[v]) swap(u, v);
        return u;
    }
    int dist(int u, int v) { return dpth[u] + dpth[v] - 2 * dpth[lca(u, v)]; }
    // make sure to update the return type based on the type of the segment
    // tree
    int query(int u, int k) { return queryPosition(ndToIdx[u], k); }

    void update(int u, int v, int p, int to_insert) {
        while (chHead[u] != chHead[v]) {
            if (dpth[chHead[v]] > dpth[chHead[u]]) {
                swap(u, v);
            }
            updateRange(ndToIdx[chHead[u]], ndToIdx[u], p, to_insert);
            u = par[chHead[u]];
        }
        if (dpth[u] > dpth[v]) {
            swap(u, v);
        }
        updateRange(ndToIdx[u], ndToIdx[v], p, to_insert);
    }
} hld;
template <typename T>
class FenwickTree {
   public:
    vector<T> tree;
    int n;
    void init(int n) {
        tree.assign(n + 2, 0);
        this->n = n;
    }
    T mrg(T &x, T &y) { return x + y; }

    void upd(int x, T v) {
        for (; x <= n; x += (x) & (-x)) {
            tree[x] = mrg(tree[x], v);
        }
    }
    T getprefix(int x) {
        if (x <= 0) return 0;
        T rs = 0;
        for (; x; x -= (x) & (-x)) {
            rs = mrg(rs, tree[x]);
        }
        return rs;
    }
    T getrange(int l, int r) { return getprefix(r) - getprefix(l - 1); }
};
FenwickTree<ll> ft;

void solve_1() {
    for (int i = 0; i < q; i++) {
        cin >> t >> p >> u;
        p--;
        u--;
        if (t == 1) {
            v[p] = u;
        } else {
            if (v[0] == u) {
                cout << 0 << endl;
            } else {
                cout << -1 << endl;
            }
        }
    }
}

void solve_2() {
    for (int i = 0; i < q; i++) {
        cin >> t >> p >> u;
        p--;
        u--;
        if (t == 1) {
            v[p] = u;
        } else {
            if (hld.dist(v[0], u) + hld.dist(v[1], u) == hld.dist(v[0], v[1])) {
                cout << hld.dist(v[p], u) << endl;
            } else {
                cout << -1 << endl;
            }
        }
    }
}

void solve() {
    for (int i = 0; i < q; i++) {
        cin >> t >> p >> u;
        --u, --p;
        if (t == 1) {
            int d = hld.dist(v[p], v[(p + 1) % k]);
            ft.upd(p + 1, -d);
            hld.update(v[p], v[(p + 1) % k], p, 0);

            int b = (p + k - 1) % k;
            d = hld.dist(v[p], v[b]);
            hld.update(v[b], v[p], b, 0);
            ft.upd(b+1, -d);
            v[p] = u;
            d = hld.dist(v[p], v[(p + 1) % k]);
            ft.upd(p + 1, d);
            hld.update(v[p], v[(p + 1) % k], p, 1);
            d = hld.dist(v[p], v[b]);
            ft.upd(b+1, d);
            hld.update(v[b], v[p], b, 1);
        } else {
            int pos = hld.query(u, p);
            if (pos == -1) {
                cout << -1 << endl;
                continue;
            }
            ll dist = hld.dist(v[pos], u);

            if (pos >= p) {
                dist += ft.getrange(p + 1, pos);
            } else {
                dist += ft.getrange(p + 1, k);
                dist += ft.getprefix(pos);
            }
            cout << dist << endl;
        }
    }
}

void test_case() {
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        cin >> v[i];
        --v[i];
    }
    adj.init(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj.addBiEdge(u, v);
    }
    ft.init(k + 1);
    hld.run(adj);
    for (int i = 0; i < k; i++) {
        hld.update(v[i], v[(i + 1) % k], i, 1);
        ft.upd(i + 1, hld.dist(v[i], v[(i + 1) % k]));
    }
    cin >> q;
    if (k == 1) {
        solve_1();
    } else if (k == 2) {
        solve_2();
    } else {
        solve();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    test_case();
    return 0;
}