Only add problems when they are needed.

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define endl '\n'
using namespace std;
typedef long long ll;
 
const int N = 105;
 
int T, n, a[N], b[N];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    for(cin >> T; T; --T) {
        cin >> n;
        rep(i, 1, n) cin >> a[i];
        rep(i, 1, n) cin >> b[i];
        int diff = 0, ans = 0;
        rep(i, 1, n) {
            if(a[i - diff] > b[i]) {
                ++ans;
                ++diff;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Is there anything that never / always changes after each operation?

The parity.

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define endl '\n'
using namespace std;
typedef long long ll;
 
int T, n;
string s;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    for(cin >> T; T; --T) {
        cin >> n >> s;
        int cntU = 0;
        for(char c : s) if(c == 'U') ++cntU;
        if(cntU & 1) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

What's the answer if $$$a_1=a_2=\cdots=a_n$$$ and $$$k=0$$$?

What's the answer if $$$k=0$$$?

You've already known the $$$\mathcal O(k)$$$ solution. How to improve it?

#include<bits/stdc++.h>
using namespace std;
void solve()
{
    int n;long long k;
    cin>>n>>k;
    vector<long long>a(n);
    for(int x=0;x<n;x++)
    cin>>a[x];
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    long long lst=a.back(),cnt=1;
    a.pop_back();
    while(!a.empty()&&lst==a.back())a.pop_back(),cnt++;
    while(!a.empty())
    {
        long long delta=a.back()-lst;
        if(k<delta*cnt)break;
        k-=delta*cnt;
        lst=a.back();
        while(!a.empty()&&lst==a.back())a.pop_back(),cnt++;
    }
    lst+=k/cnt;
    k%=cnt;
    cnt-=k;
    cout<<lst*n-cnt+1<<endl;
}
main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
}

Denote $$$\gcd(a,b)$$$ as $$$d$$$.

Did you notice that $$$b\mid a$$$? How to prove that?

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2000005;
int tc,n,m; ll ans;
inline void solve(){
	cin>>n>>m; ans=0;
	for(int i=1;i<=m;i++)
		ans+=(n+i)/(1ll*i*i);
	cout<<ans-1<<'\n';
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>tc; while(tc--) solve();
	return 0;
}

Denote $$$\gcd(a,b)$$$ as $$$d$$$. Assume that $$$a=pd$$$ and $$$b=qd$$$.

$$$\gcd(p,q)=1$$$.

How large could $$$p$$$ and $$$q$$$ be?

#include <bits/stdc++.h>
using namespace std;
 
#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<
 
#define INF (ll)1e18
#define mod 998244353
#define maxn 110
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif
    int t;
    cin>>t;
    while(t--)
    {
        ll n,m; cin >> n>>m;
        ll sq = sqrt(n) + 2,sqm=sqrt(m)+2;
    
        vector bad(sq + 1, vector<bool>(sqm+1, 0));
        for (ll i = 2; i <= min(sq,sqm); i++) {
            for (ll a = i; a <= sq; a += i) {
                for (ll b = i; b <= sqm; b += i) {
                    bad[a][b] = true;
                }
            }
        }
    
        ll ans = 0;
        for (ll a = 1; a * a <= n; a++) {
            for (ll b = 1; b * b <= m; b++) {
                if (bad[a][b]) continue;
                ans += min(n/(a+b)/a,m/(a+b)/b);
            }
        }
        cout << ans << nl;
    }
 
    return 0;
}

The height of a Fenwick Tree is $$$\mathcal O(\log n)$$$, so operations like enumerating ancestors of each vertex will be acceptable.

What's the coefficient of $$$a_u$$$ in each $$$b$$$ value of its ancestors?

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;
 
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}
 
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
 
template<int mod>
inline unsigned int down(unsigned int x) {
	return x >= mod ? x - mod : x;
}
 
template<int mod>
struct Modint {
	unsigned int x;
	Modint() = default;
	Modint(unsigned int x) : x(x) {}
	friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
	friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
	friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
	friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
	friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
	friend Modint operator/(Modint a, Modint b) {return a * ~b;}
	friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
	friend Modint operator~(Modint a) {return a ^ (mod - 2);}
	friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
	friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
	friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
	friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
	friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
	friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
	friend Modint& operator++(Modint& a) {return a += 1;}
	friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
	friend Modint& operator--(Modint& a) {return a -= 1;}
	friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
	friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
	friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};
 
const int N = 1e6 + 100, mod = 998244353;
typedef Modint<mod> mint;
 
int T, n, k;
mint a[N], inv[N];
 
inline int lowbit(int x) {return x & -x;}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    inv[0] = inv[1] = 1;
    rep(i, 2, N - 1) inv[i] = (mod - mod / i) * inv[mod % i];
    for(cin >> T; T; --T) {
        cin >> n >> k;
        rep(i, 1, n) cin >> a[i];
        rep(i, 1, n) {
            mint mul = 1;
            for(int u = i + lowbit(i), d = 1; u <= n; u += lowbit(u), ++d) {
                mul *= (d + k - 1) * inv[d];
                a[u] -= mul * a[i];
            }
        }
        rep(i, 1, n) cout << a[i] << " \n"[i == n];
    }
    return 0;
}

Binary search on the answer of magics.

You may come up with many $$$\mathcal O(m\log m + n\log^2 m)$$$ solutions with heavy data structures. Unfortunately, none of them is helpful.

The key is to judge $$$\mathcal O(m\log n)$$$ times whether vertex $$$u$$$ is reachable from vertex $$$v$$$ in $$$k$$$ steps, instead of querying the minimal value or something else.

#include <bits/stdc++.h>
 
namespace FastIO {
	template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
	template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar(x % 10 ^ '0'); }
	template <typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x); }
	template <typename T> inline void print(T x, char en) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x), putchar(en); }
}; using namespace FastIO;
 
#define MAXM 1000001
int dep[MAXM], id[MAXM], dfn[MAXM], to[MAXM], sz[MAXM], tot = 0;
std::vector<int> ch[MAXM];
void dfs(int u) {
	sz[u] = 1, dfn[u] = ++tot;
	for (int v : ch[u]) {
		dep[v] = dep[u] + 1, id[v] = id[u];
		dfs(v), sz[u] += sz[v];
	}
}
inline bool inSub(int u, int v) /* v \in u ? */ { return dfn[u] <= dfn[v] && dfn[v] < dfn[u] + sz[u]; }
constexpr int INF = 0x3f3f3f3f;
inline int query(int u, int v) /* u -> v */ {
	if (u == v) return 0;
	if (id[u] != id[v]) return INF;
	int res = INF;
	if (inSub(v, u)) res = dep[u] - dep[v];
	if (inSub(v, to[id[u]])) res = std::min(dep[u] - dep[v] + dep[to[id[u]]] + 1, res);
	// printf("query(%d, %d) = %d\n", u, v, res);
	return res;
}
 
#define MAXN 1000001
int a[MAXN], N, M;
bool check(int val) {
	// printf("check %d\n", val);
	int lst = 1;
	for (int i = 1; i <= N; ++i) {
		while (lst <= M && query(a[i], lst) > val) ++lst;
		if (lst > M) return false;
		// printf("a[%d] = %d\n", i, lst);	
	}
	return true;
}
 
namespace DSU {
	int fa[MAXM];
	void inis(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }
	inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
	inline bool merge(int x, int y) { if (find(x) == find(y)) return false; fa[fa[x]] = fa[y]; return true; }
}; using namespace DSU;
 
int main() {
	int T = read<int>();
	while (T--) {
		N = read<int>(), M = read<int>(), inis(M);
		for (int i = 1; i <= N; ++i) a[i] = read<int>();
		for (int x = 1; x <= M; ++x) dep[x] = id[x] = dfn[x] = to[x] = sz[x] = 0, ch[x].clear();
		tot = 0;
		for (int i = 1, p; i <= M; ++i) {
			p = read<int>();
			if (merge(i, p)) ch[p].push_back(i); else to[i] = p;
		}
		for (int i = 1; i <= M; ++i) if (to[i] > 0) id[i] = i, dfs(i);
		if (!check(M)) { puts("-1"); continue; }
		int L = 0, R = M;
		while (L < R) {
			int mid = L + R >> 1;
			if (check(mid)) R = mid; else L = mid + 1;
		}
		print<int>(R, '\n');
	}
}

Use the simplest way to judge if an $$$a$$$ is valid.

We've got a $$$\mathcal O(nm)$$$ solution. Our target time complexity is $$$\mathcal O(n\sqrt{n})$$$.

It can be boiled down to a grid path counting problem.

#include <bits/stdc++.h>
 
namespace FastIO {
	template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
	template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar(x % 10 ^ '0'); }
	template <typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x); }
	template <typename T> inline void print(T x, char en) { if (x < 0) putchar('-'), x = -x; else if (x == 0) putchar('0'); write<T>(x), putchar(en); }
}; using namespace FastIO;
 
#define MAXN 2000001
namespace Maths {
	constexpr int MOD = 998244353;
	long long qpow(long long a, long long x) { long long ans = 1; while (x) (x & 1) && (ans = ans * a % MOD), a = a * a % MOD, x >>= 1; return ans; }
	long long frac[MAXN << 1 | 1], prac[MAXN << 1 | 1];
	inline void inis(int V = MAXN * 2) { frac[0] = prac[0] = 1; for (int i = 1; i <= V; ++i) frac[i] = frac[i - 1] * i % MOD; prac[V] = qpow(frac[V], MOD - 2); for (int i = V - 1; i; --i) prac[i] = prac[i + 1] * (i + 1) % MOD; }
	inline long long C(int N, int M) { if (N < 0 || M < 0 || N < M) return 0; return frac[N] * prac[M] % MOD * prac[N - M] % MOD; }
}; using namespace Maths;
 
struct Point {
	int x, y;
	Point () {}
	Point (int X, int Y) : x(X), y(Y) {}
	inline void flip(int b) { x += b, y -= b, std::swap(x, y); }
	inline int calc() { return C(x + y, y); }
} pA, pB;
 
inline void add(int& x, int y) { (x += y) >= MOD && (x -= MOD); }
inline void del(int& x, int y) { (x -= y) < 0 && (x += MOD); }
 
int calc(int p, int q, int b1, int b2) {
	pA = pB = Point(p, q);
	int ans = pA.calc();
	while (pA.x >= 0 && pA.y >= 0) 
		pA.flip(b1), del(ans, pA.calc()), pA.flip(b2), add(ans, pA.calc());
	while (pB.x >= 0 && pB.y >= 0) 
		pB.flip(b2), del(ans, pB.calc()), pB.flip(b1), add(ans, pB.calc());
	return ans;
}
 
int dp[2][3001], powm[MAXN];
void solve() {
	int N = read<int>(), M = read<int>(), b0 = read<int>();
	if (b0 >= M) return (void)print<int>(qpow(M, N), '\n');
	powm[0] = 1; for (int i = 1; i <= N; ++i) powm[i] = 1ll * M * powm[i - 1] % MOD;
	if (1ll * M * M <= N) { // dp
		for (int k = 0; k < M; ++k) dp[0][k] = (int)(k == b0), dp[1][k] = 0;
		int ans = 1ll * dp[0][M - 1] * (M - 1) % MOD * powm[N - 1] % MOD;
		for (int i = 1; i <= N; ++i) {
			auto now = dp[i & 1], lst = dp[(i & 1) ^ 1];
			now[0] = 0; for (int k = 0; k + 1 < M; ++k) now[k + 1] = 1ll * lst[k] * (M - 1) % MOD;
			for (int k = 1; k < M; ++k) add(now[k - 1], lst[k]);
			if (i < N) add(ans, 1ll * now[M - 1] * (M - 1) % MOD * powm[N - i - 1] % MOD);
		}
		for (int k = 0; k < M; ++k) add(ans, dp[N & 1][k]);
		print<int>(ans, '\n');
	} else { // reflective inclusion-exclusion
		const int B1 = M - b0, B2 = -1 - b0; int ans = qpow(M, N);
		for (int x = b0, y = 0, k = 1, p = b0; p < N; p += 2, ++x, ++y, k = 1ll * k * (M - 1) % MOD) 
			del(ans, 1ll * calc(x, y, B1, B2) * k % MOD * powm[N - p - 1] % MOD);
		print<int>(ans, '\n');
	}
}
 
int main() { int T = read<int>(); inis(); while (T--) solve(); return 0; }

Solve E1 with $$$\mathcal O(n\sqrt{n})$$$ solution first (The $$$\mathcal O(n\log^2n)$$$ solution doesn't help much in E2).

For a single round of inclusion-exclusion, write down the form of the answer as simple as possible.

#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 998244353;
const int N = 2e6+5;
int inv[N];
 
int inversemod(int p, int q) {
  // assumes p > 0
  // https://codeforces.me/blog/entry/23365
  return (p > 1 ? q-1LL*inversemod(q%p, p)*q/p : 1);
}
 
void add(int& x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
}
 
void sub(int& x, int y) {
  x -= y;
  if (x < 0) x += MOD;
}
 
int solve(int n, int m, int b0) {
  // let X = hit -1, Y = hit m
  // f(S) = count of sequences that end up in [0, infty] while containing the pattern S
  // g(S) = count of sequences that end up in [-infty, -1] while containing the pattern S
  // we want f() - f(X) + f(YX) - f(XYX) + f(YXYX) - f(XYXYX) + ...
  //             + g(Y) - g(XY) + g(YXY) - g(XYXY) + g(YXYXY) - ...
  vector<int> pw(n+1);
  pw[0] = 1;
  for (int i = 1; i <= n; i++) pw[i] = 1LL*pw[i-1]*(m-1) % MOD;
 
  // final ans will be sum from i = 0 to n of (n choose i) a_i
  vector<int> a(n+2);
  auto work = [&] (int c, int pw_coeff, int sgn_x) -> bool {
    // let RANGE = [-infty, -1] if sgn_x == -1 and [0, infty] if sgn_x == 1
    // for all x in RANGE such that (n+x+c)/2 is between 0 and n inclusive,
    // add pw_coeff*pw[(n+x-b0)/2] to a[(n+x+c)/2]
 
    // return 0 to signal that we are out of bounds and should exit, otherwise 1
    int l = 0;
    if (sgn_x == 1) l = max(l, (n+c+1)>>1);
    int r = n;
    if (sgn_x == -1) r = min(r, (n+c-1)>>1);
    if (l > r) return 0;
    add(a[l], 1LL*pw_coeff*pw[l-(b0+c)/2] % MOD);
    sub(a[r+1], 1LL*pw_coeff*pw[r+1-(b0+c)/2] % MOD);
    return 1;
  };
 
  int ans = 0;
  // f(k*YX)
  // after reflection trick, end up in x + 2*(m+1)*k
  for (int k = 0; work(2*(m+1)*k - b0, 1, 1); k++);
 
  // f(X + k*YX)
  // after reflection trick, end up in -2-x - 2*(m+1)*k
  for (int k = 0; work(2*(m+1)*k+2+b0, MOD-1, 1); k++);
 
  // g(Y + k*XY)
  // after reflection trick, end up in 2*m-x + 2*(m+1)*k
  for (int k = 0; work(-2*m -2*(m+1)*k + b0, 1, -1); k++);
 
  // g(k*XY)
  // after reflection trick, end up in x - 2*(m+1)*k
  for (int k = 1; work(-2*(m+1)*k - b0, MOD-1, -1); k++);
 
  for (int i = 1; i <= n; i++) {
    add(a[i], 1LL*a[i-1]*(m-1) % MOD);
  }
 
  // do the binomial stuff without precalculated factorials because why not
  int coeff = 1;
  for (int i = 0; i <= n; i++) {
    add(ans, 1LL * coeff * a[i] % MOD);
    coeff = 1LL * coeff * (n-i) % MOD * inv[i+1] % MOD;
  }
 
  return ans;
}
 
int main () {
  ios_base::sync_with_stdio(0); cin.tie(0);
  inv[1] = 1;
  for (int i = 2; i < N; i++) inv[i] = 1LL*(MOD-MOD/i)*inv[MOD % i] % MOD;
 
  int T;
  cin >> T;
  while (T--) {
    int n, m, b0;
    cin >> n >> m >> b0;
    if (b0 >= m) {
      int ans = 1;
      for (int i = 0; i < n; i++) ans = 1LL*ans*m % MOD;
      cout << ans << '\n';
      continue;
    }
    cout << solve(n, m, b0) << '\n';
  }
}

How to maintain $$$\sum\min(nxt_i-pre_i,x)$$$? Try $$$\sum\min(nxt_i-i,x)+\min(i-pre_i,x)$$$.

To maintain $$$\sum\min(nxt_i-i,x)$$$, we can use chunking. Just +1 and $$$\operatorname{chkmin}$$$.

To finish it, consider what we do in segment-beats.

#include<bits/stdc++.h>
using namespace std;
 
constexpr int maxn=300010,maxq=100010,B=400;
 
int n,bn,a[maxn],b[maxn],idx[maxn],nxt[maxn],add[maxn/B+5],mxadd[maxn/B+5],mx[maxn/B+5],se[maxn/B+5],t[maxn];
long long ans[maxq];
vector<int>val[maxn/B+5],mxval[maxn/B+5],pre[maxn/B+5],mxpre[maxn/B+5],pos[maxn/B+5],ks[maxn];
 
void vAdd(int i)
{
	for(;i<=n;i+=(i&-i)) t[i]++;
}
 
int nQuery(int i)
{
	int s=0;
	for(;i;i-=(i&-i)) s+=t[i];
	return s;
}
 
void vWork()
{
	int i,j,tot=0;
	for(i=1;i<=n;i++) b[a[i]]=i;
	for(i=1;i<=n;i++)
	{
		int p=b[i],bp=(p-1)/B+1;
		val[bp].clear();
		mxval[bp].clear();
		auto radixsort=[](vector<int>&v)
		{
			if(v.empty()) return;
			static int buc[1024],res[B+5];
			auto tmp=minmax_element(v.begin(),v.end());
			int mn=*tmp.first,rg=*tmp.second-mn;
			if(!rg) return;
			int lv=__lg(rg)/2+1,len=1<<lv,i;
			memset(buc,0,len*4);
			for(int &it:v) it-=mn,buc[it&(len-1)]++;
			for(i=1;i<len;i++) buc[i]+=buc[i-1];
			for(int it:v) res[--buc[it&(len-1)]]=it;
			memset(buc,0,len*4);
			for(int it:v) buc[it>>lv]++;
			for(i=1;i<len;i++) buc[i]+=buc[i-1];
			for(i=v.size()-1;i>=0;i--) v[--buc[res[i]>>lv]]=res[i]+mn;
		};
		auto getpre=[&](vector<int>&pre,const vector<int>&ori)
		{
			pre.resize(ori.size());
			if(ori.empty()) return;
			pre[0]=ori[0];
			for(int i=1;i<(int)ori.size();i++) pre[i]=pre[i-1]+ori[i];
		};
		int lstmx=mx[bp];
		vAdd(p);
		idx[p]=nQuery(p);
		mx[bp]=nxt[p]=n*2;
		se[bp]=0;
		auto it=pos[bp].begin();
		for(;it<pos[bp].end();it++)
		{
			j=*it;
			if(j>p) break;
			nxt[j]+=add[bp];
			if(nxt[j]>lstmx) nxt[j]+=mxadd[bp];
			nxt[j]=min(nxt[j],idx[p]);
			idx[j]+=add[bp];
			if(nxt[j]>mx[bp]) se[bp]=mx[bp],mx[bp]=nxt[j];
			else if(nxt[j]>se[bp]) se[bp]=nxt[j];
		}
		it=pos[bp].insert(it,p);
		for(it++;it!=pos[bp].end();it++)
		{
			j=*it;
			nxt[j]+=add[bp];
			if(nxt[j]>lstmx) nxt[j]+=mxadd[bp];
			nxt[j]++;
			idx[j]+=add[bp]+1;
			if(nxt[j]>mx[bp]) se[bp]=mx[bp],mx[bp]=nxt[j];
			else if(nxt[j]>se[bp]) se[bp]=nxt[j];
		}
		for(int j:pos[bp])
		{
			if(nxt[j]==mx[bp]) mxval[bp].push_back(nxt[j]-idx[j]);
			else val[bp].push_back(nxt[j]-idx[j]);
		}
		add[bp]=mxadd[bp]=0;
		radixsort(val[bp]);
		getpre(pre[bp],val[bp]);
		radixsort(mxval[bp]);
		getpre(mxpre[bp],mxval[bp]);
		for(j=bp+1;j<=bn;j++) add[j]++,mx[j]++,se[j]++;
		for(j=1;j<bp;j++)
		{
			if(mx[j]<=idx[p]) continue;
			if(se[j]<idx[p])
			{
				mxadd[j]+=idx[p]-mx[j],mx[j]=idx[p];
				continue;
			}
			val[j].clear();
			mxval[j].clear();
			lstmx=mx[j];
			mx[j]=idx[p],se[j]=0;
			for(int x:pos[j])
			{
				nxt[x]+=add[j];
				idx[x]+=add[j];
				if(nxt[x]>lstmx) nxt[x]+=mxadd[j];
				if(nxt[x]>=idx[p])
				{
					nxt[x]=idx[p];
					mxval[j].push_back(nxt[x]-idx[x]);
				}
				else
				{
					if(nxt[x]>se[j]) se[j]=nxt[x];
					val[j].push_back(nxt[x]-idx[x]);
				}
			}
			add[j]=mxadd[j]=0;
			radixsort(val[j]);
			getpre(pre[j],val[j]);
			radixsort(mxval[j]);
			getpre(mxpre[j],mxval[j]);
		}
		for(int ki:ks[i])
		{
			tot++;
			for(j=1;j<=bn;j++)
			{
				auto it=lower_bound(val[j].begin(),val[j].end(),ki);
				ans[tot]+=(val[j].end()-it)*ki;
				if(it!=val[j].begin()) ans[tot]+=pre[j][it-val[j].begin()-1];
				it=lower_bound(mxval[j].begin(),mxval[j].end(),ki-mxadd[j]);
				ans[tot]+=(mxval[j].end()-it)*ki;
				if(it!=mxval[j].begin()) ans[tot]+=(it-mxval[j].begin())*mxadd[j]+mxpre[j][it-mxval[j].begin()-1];
			}
		}
	}
}
 
int main()
{
	ios::sync_with_stdio(false),cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
    	int i,ki,tot=0;
    	cin>>n;
    	bn=(n-1)/B+1;
    	for(i=1;i<=n;i++) cin>>a[i];
    	for(i=1;i<=n;i++)
    	{
    		cin>>ki;
    		ks[i].resize(ki);
    		for(int &it:ks[i])
    		{
    			cin>>it;
    			ans[++tot]=-(i+it-1);
    		}
    	}
    	vWork();
    	reverse(a+1,a+n+1);
    	for(int x=1;x<=n;x++)
    	t[x]=0;
    	for(i=1;i<=bn;i++) mx[i]=0,se[i]=0,val[i].clear(),mxval[i].clear(),pos[i].clear();
    	vWork();
    	for(int x=1;x<=n;x++)
    	t[x]=0;
    	for(i=1;i<=bn;i++) mx[i]=0,se[i]=0,val[i].clear(),mxval[i].clear(),pos[i].clear();
    	for(i=1;i<=tot;i++) cout<<ans[i]<<'\n';
    	tot=0;
	}
	return 0;
}

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
 
#define y1 y114514
int T, n, m, x1, y1, x2, y2;
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
int f(int x, int y) {
	if((x == 1 || x == n) && (y == 1 || y == m)) return 2;
	if(x == 1 || x == n || y == 1 || y == m) return 3;
	return 4;
}
 
int main() {
	for(scanf("%d", &T);T;T--) {
		scanf("%d%d%d%d%d%d", &n, &m, &x1, &y1, &x2, &y2);
		printf("%d\n", min(f(x1, y1), f(x2, y2)));
	}
	return 0;
}

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 1e3+5;
 
int T, n, k, a[N][N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
 
int main() {
	for(scanf("%d", &T);T;T--) {
		scanf("%d%d", &n, &k);
		rep(i, 1, n) rep(j, 1, n) scanf("%d", &a[i][j]);
		int diff = 0;
		rep(i, 1, n) rep(j, 1, n) if(a[i][j] != a[n+1-i][n+1-j]) ++diff;
		diff /= 2;
		if(diff > k) puts("NO");
		else {
			k -= diff;
			if(n & 1) puts("YES");
			else if(k & 1) puts("NO");
			else puts("YES");
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
int T, n, m;
 
int ask(int x, int y) {
	printf("? %d %d\n", x, y);
	fflush(stdout);
	scanf("%d", &x);
	return x;
}
 
void give(int x, int y) {
	printf("! %d %d\n", x, y);
	fflush(stdout);
}
 
int main() {
	for(scanf("%d", &T);T;T--) {
		scanf("%d%d", &n, &m);
		int T1 = ask(1, 1);
		if(T1 >= n) {
			int T2 = ask(1, T1+1);
			give(T2+1, T1+1);
		}
		else if(T1 >= m) {
			int T2 = ask(T1+1, 1);
			give(T1+1, T2+1);
		}
		else {
			int T2 = ask(T1+1, 1);
			int T3 = ask(1, T1+1);
			if(T2 == T1 && T3 == T1) give(T1+1, T1+1);
			else if(T3 == T1) give(T1+1, T2+1);
			else give(T3+1, T1+1);
		}
	}
	return 0;
}

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=y;x<=z;x++)
#define per(x,y,z) for(ll x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 1e5+5; 
 
ll n, m, a[N], sz[N], son[N], fa[N], sum[N];
vector<ll> e[N];
set<tuple<ll, ll> > sons[N]; 
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
void dfs(ll u, ll f) {
	sz[u] = 1;
	sum[u] = a[u];
	fa[u] = f;
	for(auto v : e[u]) {
		if(v == f) continue;
		dfs(v, u);
		sz[u] += sz[v];
		sum[u] += sum[v];
		sons[u].insert(make_tuple(-sz[v], v));
		if(sz[v] > sz[son[u]] || sz[v] == sz[son[u]] && v < son[u]) son[u] = v;
	}
}
 
int main() {
	scanf("%lld%lld", &n, &m);
	rep(i, 1, n) scanf("%lld", &a[i]);
	rep(i, 1, n-1) {
		ll u, v;
		scanf("%lld%lld", &u, &v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1, 0);
	while(m --> 0) {
		ll op, u;
		scanf("%lld%lld", &op, &u);
		if(op == 1) printf("%lld\n", sum[u]);
		else {
			ll v = son[u];
			if(!v) continue;
			ll p = fa[u];
			sz[u] -= sz[v];
			sum[u] -= sum[v];
			sons[u].erase(make_tuple(-sz[v], v));
			son[u] = sons[u].empty() ? 0 : get<1>(*sons[u].begin());
			fa[u] = v;
			sz[v] += sz[u];
			sum[v] += sum[u];
			sons[v].insert(make_tuple(-sz[u], u));
			son[v] = get<1>(*sons[v].begin());
			fa[v] = p;
			sons[p].erase(make_tuple(-sz[v], u));
			sons[p].insert(make_tuple(-sz[v], v));
			son[p] = get<1>(*sons[p].begin());
		}
	}
	return 0;
}

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, P = 4e5 + 5, K = 5e6 + 5, W = 5e6; 
 
int n, m, a[N], tab[K], phi[K], p[P], pcnt, dis[K], fa[K][6];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
void sieve(int lim) {
	phi[1] = 1;
	rep(i, 2, lim) {
		if(!tab[i]) {
			p[++pcnt] = i;
			phi[i] = i - 1;
		}
		for(int j=1;j<=pcnt&&1LL*i*p[j]<=lim;j++) {
			tab[i*p[j]] = 1;
			if(i % p[j]) phi[i*p[j]] = phi[i] * phi[p[j]];
			else {
				phi[i*p[j]] = phi[i] * p[j];
				break;
			}
		}
	}
}
void initTree(int lim) {
	dis[1] = 1;
	rep(j, 0, 5) fa[1][j] = 1;
	rep(i, 2, lim) {
		dis[i] = dis[phi[i]] + 1;
		fa[i][0] = phi[i];
		rep(j, 1, 5) fa[i][j] = fa[fa[i][j-1]][j-1];
	}
}
int LCA(int u, int v) {
	if(dis[u] < dis[v]) swap(u, v);
	per(i, 5, 0) if(dis[fa[u][i]] >= dis[v]) u = fa[u][i];
	if(u == v) return u;
	per(i, 5, 0) if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}
struct Node {
	int lca, ans, mndis, allrt;
};
struct SegTree {
	Node t[N<<2];
	#define lc(u) (u<<1)
	#define rc(u) (u<<1|1)
	void pushup(int u, int l, int r) {
		int mid = (l + r) >> 1;
		t[u].lca = LCA(t[lc(u)].lca, t[rc(u)].lca);
		t[u].ans = t[lc(u)].ans + t[rc(u)].ans
				 + (mid - l + 1) * (dis[t[lc(u)].lca] - dis[t[u].lca])
				 + (r - mid) * (dis[t[rc(u)].lca] - dis[t[u].lca]);
		t[u].mndis = min(t[lc(u)].mndis, t[rc(u)].mndis);
		t[u].allrt = t[lc(u)].allrt && t[rc(u)].allrt;
	}
	void build(int u, int l, int r) {
		if(l == r) {
			t[u].lca = a[l];
			t[u].ans = 0;
			t[u].mndis = dis[a[l]];
			t[u].allrt = a[l] == 1;
			return;
		}
		int mid = (l + r) >> 1;
		build(lc(u), l, mid);
		build(rc(u), mid+1, r);
		pushup(u, l, r);
	}
	void modify(int u, int l, int r, int ql, int qr) {
		if(t[u].allrt) return;
		if(l == r) {
			t[u].lca = fa[t[u].lca][0];
			--t[u].mndis;
			t[u].allrt = t[u].lca == 1;
			return;
		}
		int mid = (l + r) >> 1;
		if(ql <= mid) modify(lc(u), l, mid, ql, qr);
		if(qr > mid) modify(rc(u), mid+1, r, ql, qr);
		pushup(u, l, r);
	}
	int queryLCA(int u, int l, int r, int ql, int qr) {
		if(ql <= l && r <= qr) return t[u].lca;
		int mid = (l + r) >> 1;
		if(qr <= mid) return queryLCA(lc(u), l, mid, ql, qr);
		if(ql > mid) return queryLCA(rc(u), mid+1, r, ql, qr);
		int ans = queryLCA(lc(u), l, mid, ql, qr);
		if(ans == 1) return 1;
		return LCA(ans, queryLCA(rc(u), mid+1, r, ql, qr));
	}
	int queryAns(int u, int l, int r, int ql, int qr, int lca) {
		if(ql <= l && r <= qr) {
			return t[u].ans + (r - l + 1) * (dis[t[u].lca] - dis[lca]);
		}
		int mid = (l + r) >> 1, ans = 0;
		if(ql <= mid) ans += queryAns(lc(u), l, mid, ql, qr, lca);
		if(qr > mid) ans += queryAns(rc(u), mid+1, r, ql, qr, lca);
		return ans;
	}
	#undef lc
	#undef rc
}sgt;
 
int main() {
	sieve(W);
	initTree(W);
	scanf("%d%d", &n, &m);
	rep(i, 1, n) scanf("%d", &a[i]);
	sgt.build(1, 1, n);
	while(m --> 0) {
		int op, l, r;
		scanf("%d%d%d", &op, &l, &r);
		if(op == 1) sgt.modify(1, 1, n, l, r);
		else {
			int lca = sgt.queryLCA(1, 1, n, l, r);
			printf("%d\n", sgt.queryAns(1, 1, n, l, r, lca));
		}
	}
	return 0;
}

// Celtic
#include<bits/stdc++.h> 
#define N 501001
#define MAX 2005
using namespace std;
typedef long long ll;
typedef long double db;
const ll inf=1e18,mod=998244353,inv3=(mod+1)/3;
inline void read(ll &ret)
{
	ret=0;char c=getchar();bool pd=false;
	while(!isdigit(c)){pd|=c=='-';c=getchar();}
	while(isdigit(c)){ret=(ret<<1)+(ret<<3)+(c&15);c=getchar();}
	ret=pd?-ret:ret;
	return;
}
ll n,m,x,y,siz[N],son[N],minn=inf,num=0,f[N],sum,root;
vector<ll>v[N];
bool vis[N];
inline void find(ll ver,ll fa)
{
	siz[ver]=1;
	ll maxn=0;
	for(int i=0;i<v[ver].size();i++)
	{
		ll to=v[ver][i];
		if(to==fa||vis[to])
			continue;
		find(to,ver);
		siz[ver]+=siz[to];
		maxn=max(maxn,siz[to]);
	}
	maxn=max(maxn,num-siz[ver]);
	if(maxn<minn)
	{
		minn=maxn;
		root=ver;
	}
	return;
}
ll valmx[N],valmn[N],sz[N],now,fat[N];
struct node
{
	ll x,y,ver;
}a[N];
inline bool cmp1(node a,node b)
{
	return a.x<b.x;
}
inline bool cmp2(node a,node b)
{
	return a.y<b.y;
}
ll cnt;
vector<ll>g[N];
inline void dfs(ll ver,ll fa,ll d)
{
	valmx[ver]=max(valmx[fa],ver);
	valmn[ver]=min(valmn[fa],ver);
	if(ver!=now)
	{
		if(valmx[ver]==ver||valmx[ver]==now)
			sum++;
		if(valmn[ver]==ver||valmn[ver]==now)
			sum++;
		if(valmx[ver]==ver&&valmn[ver]==now)
			sum-=2;
		if(valmx[ver]==now&&valmn[ver]==ver)
			sum-=2;
		if(valmn[ver]==ver)
			f[now]++;
		if(valmn[ver]==now)
			f[ver]++;
		g[d].push_back(ver);
		a[++cnt]=node{valmx[ver],valmn[ver],ver};
	}
	sz[ver]=1;
	fat[ver]=d;
//	cout<<"dfs"<<ver<<" "<<fa<<" "<<d<<endl;
	for(int i=0;i<v[ver].size();i++)
	{
		ll to=v[ver][i];
		if(to==fa||vis[to])
			continue;
		if(ver==now)
			dfs(to,ver,to);
		else
			dfs(to,ver,d);
		sz[ver]+=sz[to];
	}
	return;
}
ll tree[N];
inline void update(ll pos,ll num)
{
	pos++;
	while(pos<N)
	{
		tree[pos]+=num;
		pos+=pos&-pos;
	}
	return;
}
inline ll query(ll pos)
{
	pos++;
	ll ret=0;
	while(pos)
	{
		ret+=tree[pos];
		pos-=pos&-pos; 
	}
	return ret;
}
inline void calc()
{
	sort(a+1,a+cnt+1,cmp1);
	for(int i=1;i<=cnt;i++)
	{
		ll j=i;
		for(;j<=cnt&&a[j].x==a[i].x;j++);
		j--;
		for(int k=i;k<=j;k++)
		{
			if(a[k].x==a[k].ver)
				sum+=i-1,sum-=2*query(a[k].y)/*,cout<<"del "<<a[k].ver<<" "<<i-1<<" "<<query(a[k].y)<<endl*/;
		}
		for(int k=i;k<=j;k++)
		{
			if(a[k].y==a[k].ver)
				update(a[k].y,1);
		}
		i=j;
	}
	for(int i=1;i<=cnt;i++)
	{
		ll j=i;
		for(;j<=cnt&&a[j].x==a[i].x;j++);
		j--;
		for(int k=i;k<=j;k++)
		{
			if(a[k].y==a[k].ver)
				update(a[k].y,-1);
		}
		i=j;
	}
	sort(a+1,a+cnt+1,cmp2);
	for(int i=cnt;i;i--)
	{
		ll j=i;
		for(;j&&a[j].y==a[i].y;j--);
		j++;
		for(int k=j;k<=i;k++)
		{
			if(a[k].y==a[k].ver)
				sum+=cnt-i;
		}
		i=j;
	}
	ll tmp=0;
	for(int i=1;i<=cnt;i++)
	{
		ll j=i;
		for(;j<=cnt&&a[j].y==a[i].y;j++);
		j--;
		for(int k=i;k<=j;k++)
			f[a[k].ver]+=tmp;
		for(int k=i;k<=j;k++)
			if(a[k].ver==a[k].y)
				tmp++;
		i=j;
	}
	return;
}
inline void decalc()
{
	sort(a+1,a+cnt+1,cmp1);
	for(int i=1;i<=cnt;i++)
	{
		ll j=i;
		for(;j<=cnt&&a[j].x==a[i].x;j++);
		j--;
		for(int k=i;k<=j;k++)
		{
			if(a[k].x==a[k].ver)
				sum-=i-1,sum+=2*query(a[k].y)/*,cout<<"back"<<a[k].ver<<" "<<i-1<<" "<<query(a[k].y)<<endl*/;
		}
		for(int k=i;k<=j;k++)
		{
			if(a[k].y==a[k].ver)
				update(a[k].y,1);
		}
		i=j;
	}
	for(int i=1;i<=cnt;i++)
	{
		ll j=i;
		for(;j<=cnt&&a[j].x==a[i].x;j++);
		j--;
		for(int k=i;k<=j;k++)
		{
			if(a[k].y==a[k].ver)
				update(a[k].y,-1);
		}
		i=j;
	}
	sort(a+1,a+cnt+1,cmp2);
	for(int i=cnt;i;i--)
	{
		ll j=i;
		for(;j&&a[j].y==a[i].y;j--);
		j++;
		for(int k=j;k<=i;k++)
		{
			if(a[k].y==a[k].ver)
				sum-=cnt-i;
		}
		i=j;
	}
	ll tmp=0;
	for(int i=1;i<=cnt;i++)
	{
		ll j=i;
		for(;j<=cnt&&a[j].y==a[i].y;j++);
		j--;
		for(int k=i;k<=j;k++)
			f[a[k].ver]-=tmp;
		for(int k=i;k<=j;k++)
			if(a[k].ver==a[k].y)
				tmp++;
		i=j;
	}
	return;
}
inline void divide(ll ver)
{
	vis[ver]=true;
	now=ver;
	cnt=0;
	valmn[0]=inf;
	dfs(ver,0,0);
//	cout<<"??"<<ver<<" "<<sum<<endl;
/*	cout<<ver<<endl;
	for(int i=1;i<=cnt;i++)
		cout<<a[i].x<<" "<<a[i].y<<endl;*/
	calc();
//	cout<<ver<<" "<<cnt<<endl;
	for(int i=0;i<v[ver].size();i++)
	{
		ll to=v[ver][i];
		if(vis[to])
			continue;
		cnt=0;
		for(auto x:g[to])
			a[++cnt]=node{valmx[x],valmn[x],x}/*,cout<<ver<<" "<<to<<" "<<x<<endl*/;
		g[to].clear();
	//	cout<<ver<<" "<<to<<" "<<cnt<<endl;
		decalc();
	}
//	cout<<"result::"<<ver<<" "<<sum<<endl;
	for(int i=0;i<v[ver].size();i++)
	{
		ll to=v[ver][i];
		if(vis[to])
			continue;
		num=siz[to];
		minn=inf;
		find(to,ver);
	//	cout<<ver<<" "<<to<<" "<<root<<endl;
		divide(root);
	}
	return;
}
signed main()
{
	read(n);
	for(int i=1;i<n;i++)
	{
		read(x);
		read(y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	num=n;
	find(1,0);
	divide(root);
	printf("%lld\n",sum);
/*	for(int i=1;i<=n;i++)
		cout<<f[i]<<" ";
	cout<<endl;*/
	read(m);
	for(int i=1;i<=m;i++)
	{
		ll x;
		read(x);
		n++;
		f[n]=f[x]+1;
		sum+=(n-1)-f[n];
		printf("%lld\n",sum);
	}
	exit(0);
}

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 4e5+5;
 
ll n, m, k, faMx[N], faMn[N], disMx[N], disMn[N], dfn[N], sz[N], tms;
ll A, B, C, ans;
vector<ll> eMx[N], eMn[N], reMx[N], reMn[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
struct Dsu {
	ll fa[N];
	void init(ll x) {rep(i, 1, x) fa[i] = i;}
	ll find(ll x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
	bool merge(ll x, ll y) {
		ll u = find(x), v = find(y);
		if(u == v) return 0;
		fa[u] = v;
		return 1;
	}
}dsu;
struct BIT {
	ll c[N], sz;
	void init(ll x) {sz = x; rep(i, 1, x) c[i] = 0;}
	ll lowbit(ll x) {return x & (-x);}
	void add(ll x, ll k) {for(; x <= sz; x += lowbit(x)) c[x] += k;}
	ll ask(ll x) {ll k = 0; for(; x; x -= lowbit(x)) k += c[x]; return k;}
	ll Ask(ll x, ll y) {return ask(y) - ask(x - 1);}
}bit;
void dfs1(ll u) {
	dfn[u] = ++tms;
	sz[u] = 1;
	disMx[u] = disMx[faMx[u]] + 1;
	B += disMx[u] - 1;
	for(ll v : reMx[u]) {
		dfs1(v);
		sz[u] += sz[v];
	}
}
void dfs2(ll u) {
	disMn[u] = disMn[faMn[u]] + 1;
	A += disMn[u] - 1;
	C += bit.Ask(dfn[u], dfn[u] + sz[u] - 1);
	bit.add(dfn[u], 1);
	for(ll v : reMn[u]) dfs2(v);
	bit.add(dfn[u], -1);
}
 
int main() {
	scanf("%lld", &n);
	rep(i, 1, n-1) {
		ll u, v;
		scanf("%lld%lld", &u, &v);
		if(u < v) swap(u, v);
		eMx[u].push_back(v);
		eMn[v].push_back(u);
	}
	dsu.init(n);
	rep(i, 1, n) {
		for(ll j : eMx[i]) {
			j = dsu.find(j);
			dsu.merge(j, i);
			faMx[j] = i;
			reMx[i].push_back(j);
		}
	}
	dsu.init(n);
	per(i, n, 1) {
		for(ll j : eMn[i]) {
			j = dsu.find(j);
			dsu.merge(j, i);
			faMn[j] = i;
			reMn[i].push_back(j);
		}
	}
	bit.init(n);
	dfs1(n);
	dfs2(1);
	ans = A + B - 2 * C;
	// printf("%lld + %lld - 2 * %lld = %lld\n", A, B, C, ans);
	printf("%lld\n", ans);
	for(scanf("%lld", &m); m; m--) {
		scanf("%lld", &k);
		disMn[++n] = disMn[k] + 1;
		ans += n - disMn[n];
		printf("%lld\n", ans);
	}
	return 0;
}

Li Hua is the main character in English writing exams for Chinese students. He always asks you to write letters for him.