Consider the case where $$$k=1$$$.

#include<iostream>
using namespace std;
int t,n;
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		bool ans=false;
		for(int i=1;i<=n;i++)
		{
			int x;
			cin>>x;
			if(x==100)
			 ans=true;
		}
		if(ans)
		 cout<<"Yes"<<endl;
		else
		 cout<<"No"<<endl;
	}
}

Consider for a given $$$p$$$, which elements can be placed at $$$p$$$ with one reversal operation.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define int long long
using namespace std;
int n,a,x,m,sum;
priority_queue <int> nm[2];
bool hv[2];
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
	    sum=0;
		hv[0]=hv[1]=0;
		while(!nm[0].empty()) nm[0].pop();
		while(!nm[1].empty()) nm[1].pop();
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			cin>>a;
			nm[i&1].push(a);
			sum+=a;
		}
		for(int i=1;i<=m;i++)
		{
			cin>>x;
			if((!nm[x&1].empty()&&nm[x&1].top()>=0)||!hv[x&1])
			{
				sum-=nm[x&1].top();
				nm[x&1].pop();
				hv[x&1]=1;
			}
		}
		cout<<sum<<"\n";
	}
}

Consider how to determine whether the median of an interval equals $$$x$$$.

What could be the median of each subsequence?

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=5e3+10;
int n,a[N],b[N],mid,dp[N];
void run(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    memcpy(b+1,a+1,n<<2);
    sort(b+1,b+n+1);
    mid=b[(n+1)>>1];
    for(int i=1;i<=n;i++){
        if(a[i]==mid){
            a[i]=0;
            continue;
        }
        a[i]=(a[i]>mid?1:-1);
    }
    for(int i=1,flg=0;i<=n;i++){
        dp[i]=0;
        flg=!a[i];
        if(flg and (i==1 or dp[i-1]))dp[i]=dp[i-1]+1;
        for(int j=i-3,sm=a[i];j>=0;j-=2){
            flg+=!a[j+1];
            flg+=!a[j+2];
            sm+=a[j+1]+a[j+2];
            if(abs(sm)>=flg or (j and !dp[j]))continue;
            dp[i]=max(dp[i],dp[j]+1);
        }
        // cout<<dp[i]<<" \n"[i==n];
    }
    cout<<dp[n]<<'\n';
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int T;
    cin>>T;
    while(T--)run();
}

Try to perform a prefix sum on $$$a$$$.

Consider what the upper bound of the answer is.

#include<iostream>
#include<algorithm>
using namespace std;
#define N 200010
int t,n,a[N],p[N];
pair<long long,int> b[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--)
	{
		cin>>n;
		b[0].first=0;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			b[i].first=b[i-1].first+a[i];
			b[i].second=i;
		}
		for(int i=n;i>=1;i--)
		 b[i].first=b[i-1].first;
		sort(b+1,b+n+1);
		for(int i=n;i>=1;i--)
		 p[b[i].second]=n-i+1;
		for(int i=1;i<=n;i++)
		 cout<<p[i]<<" \n"[i==n];
	}
}

Try to use $$$0$$$ and $$$2^n-1$$$ in the solution.

#include<iostream>
#include<set>
using namespace std;
int t,n;
set<long long> s;
int makeI(long long x)
{
	cout<<"I "<<x<<endl;
	int ans=0;
	cin>>ans;
	return ans;
}
int makeQ(long long y)
{
	cout<<"Q "<<y<<endl;
	int ans=0;
	cin>>ans;
	return ans;
}
int query(long long x)
{
	int res=makeQ(x);
	for(long long w:s)
	if(w>=x)
	 res--;
	return res;
}
long long guess(int n)
{
	long long pre=0;
	for(int i=n-1;i>=0;i--)
	if(query(pre|(1ll<<i))>0)
	{
		pre|=(1ll<<i);
	}
	return pre;
}
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		s.clear();
		cout<<0<<endl;
		s.insert(0);
		int res1=makeI(0);
		if(res1==1)
		{
			makeI((1ll<<n)-1);
			long long w=guess(n);
			cout<<"A "<<1<<" "<<w<<endl;
			continue;
		}
		long long c=guess(n);
		s.insert(c);
		if(c==(1ll<<n)-1)
		{
			int res2=makeI(1);
			if(res2!=res1)
			{
				cout<<"A "<<3<<" "<<c<<endl;
			}
			else
			{
				cout<<"A "<<2<<" "<<c<<endl;
			}
			continue;
		}
		int res2=makeI((1ll<<n)-1);
		if(query((1ll<<n)-1)>0)
		{
			cout<<"A "<<2<<" "<<c<<endl;
		}
		else
		{
			cout<<"A "<<3<<" "<<c<<endl;
		}
	}
}

Under what circumstances can an edge with cost $$$w$$$ be added between vertex $$$u$$$ and vertex $$$v$$$ in a new graph?

Consider divide and conquer.

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

const int S=300005;

int n,m,k;
vector<pair<int,int> > vec[S];
int fa[S],hei[S],pt[S],fa2[S];
int top,*pot[S*3],val[S*3];
long long ans;

int fnd(int x){return fa[x]==x?x:fnd(fa[x]);}
int fnd2(int x){return fa2[x]==x?x:fa2[x]=fnd2(fa2[x]);}

inline void push(int &x){pot[++top]=&x,val[top]=x;}
inline void pop(){*pot[top]=val[top],top--;}

inline void merge(int x,int y,int w)
{
    int rx=fnd(x),ry=fnd(y);
    if(rx==ry) return;
    int px=pt[rx],py=pt[ry];
    if(px!=0&&py!=0)
    {
        int rx=fnd2(px),ry=fnd2(py);
        if(rx!=ry) ans+=w,fa2[rx]=fa2[ry];
    }
    if(hei[rx]>hei[ry]) swap(rx,ry);
    push(hei[ry]),hei[ry]=max(hei[ry],hei[rx]+1);
    push(pt[ry]),pt[ry]=max(pt[ry],pt[rx]);
    push(fa[rx]),fa[rx]=ry;
}

void doit(int l,int r,int w)
{
    if(l==r) return;
    int tp=top;
    int mid=l+r>>1;
    for(int i=r;i>=mid+1;i--)
        for(auto t:vec[i]) merge(t.first,t.second,w);
    doit(l,mid,w);
    while(top>tp) pop();
    for(int i=l;i<=mid;i++)
    {
        if(!vec[i].empty()&&w==i) w++;
        for(auto t:vec[i]) merge(t.first,t.second,w);
    }
    doit(mid+1,r,w);
    while(top>tp) pop();
}

inline void slove()
{
    cin>>n>>m>>k;
    for(int i=0;i<=m;i++) vec[i].clear();
    for(int i=1,x,y,w;i<=m;i++) cin>>x>>y>>w,vec[w].emplace_back(x,y);
    vector<int> tmp;
    for(int i=1,x;i<=k;i++) cin>>x,tmp.push_back(x);
    sort(tmp.begin(),tmp.end());
    tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
    k=tmp.size();
    for(int i=1;i<=n;i++) pt[i]=0;
    for(int i=0;i<k;i++) pt[tmp[i]]=i+1;
    for(int i=1;i<=n;i++) fa[i]=i,hei[i]=1;
    for(int i=1;i<=k;i++) fa2[i]=i;
    ans=0;
    doit(0,m,0);
    for(int i=1;i<=k;i++) if(fnd2(i)!=fnd2(1)) return cout<<"-1\n",void();
    cout<<ans<<'\n';
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T-->0) slove();
    return 0;
}

What is the value of a path that passes through the centroid of a tree?

What is the value of a path that does not pass through the centroid of a tree?

This is a convolution problem. Enumerate only the terms in the polynomial with non-zero coefficients and prove that the time complexity is correct.

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
class edge{
	public:
		edge(int x, int y, int z, int zz){v = x, w = y, c = z, nxt = zz;}
		int v, w, c, nxt;
};
class graph{
	private:
		vector<int> head;vector<edge> e;
	public:
		void init(int n){head.clear(), e.clear();for (int i = 0;i <= n;i ++) head.emplace_back(-1);}
		graph(){}graph(int n){init(n);}
		inline int addedge(int u, int v, int w = 0, int c = 0){e.emplace_back(v, w, c, head[u]), head[u] = e.size() - 1;return e.size() - 1;}
		inline int add2edge(int u, int v, int w = 0){int tmp = addedge(u, v, w);addedge(v, u, w);return tmp;}
		inline int addfedge(int u, int v, int w, int c = 0){int tmp = addedge(u, v, w, c);addedge(v, u, 0, -c);return tmp;}
		inline int& h(int u){return head[u];}
		inline edge& operator[](int i){return e[i];}
}G;
const int N = 100005;ll ans[N];vi a[N];vector<ll> b[N];
int t, n, al, mns, rt, sz[N], cnt[N];
void dfs(int u, int fa){int mx = 0;sz[u] = 1;
	for (int i = G.h(u);i != -1;i = G[i].nxt){
		int v = G[i].v;if (v == fa) continue;
		dfs(v, u), sz[u] += sz[v], mx = max(mx, sz[v]);
	}mx = max(mx, al - sz[u]);
	if (mx < mns) rt = u, mns = mx;
}
void dfs1(int u, int fa, int mx, int rt){
	a[rt].push_back(max(mx, sz[u]));
	for (int i = G.h(u);i != -1;i = G[i].nxt){
		int v = G[i].v;if (v == fa) continue;
		dfs1(v, u, max(mx, sz[u] - sz[v]), rt);
	}
}
void calc(vi& a, vector<ll>& s, vi& b, int o){
	int p = upper_bound(a.begin(), a.end(), o) - a.begin();
	for (int i = 0, j;i < b.size();i ++){
		j = upper_bound(a.begin(), a.end(), b[i]) - a.begin();
		if (b[i] > o) ans[o] -= j, ans[b[i]] += j;j = max(j, p);
		if (j < a.size()) ans[o] -= a.size() - j, s[j] ++;
	}
}
void dfs2(int u, int fa){vi vc;
	for (int i = G.h(u);i != -1;i = G[i].nxt){
		int v = G[i].v, w = sz[v];if (v == fa) continue;
		ans[n - w - w] += 1ll * cnt[w] * w, cnt[w] += w, vc.push_back(w);
	}sort(vc.begin(), vc.end()), vc.erase(unique(vc.begin(), vc.end()), vc.end());
	for (int x : vc) for (int y : vc) if (x < y)
	ans[n - x - y] += 1ll * cnt[x] * cnt[y];
	for (int v : vc) ans[n - v] += (u != rt) * cnt[v], cnt[v] = 0;
	for (int i = G.h(u);i != -1;i = G[i].nxt){
	int v = G[i].v;if (v != fa) dfs2(v, u);}
}
void solve(int u){vi to;
	for (int i = G.h(u);i != -1;i = G[i].nxt){
		int v = G[i].v;to.push_back(v), dfs1(v, u, 0, v);
		sort(a[v].begin(), a[v].end()), b[v].resize(a[v].size(), 0);
	}
	for (int x : to) if (sz[x] * 3 >= n) for (int y : to) if (x < y || sz[y] * 3 < n) calc(a[x], b[x], a[y], n - sz[x] - sz[y]);
	for (int v : to){ll ls = 0;
		for (ll& x : b[v]) ls = x += ls;
		for (int i = 0;i < a[v].size();i ++)
		ans[max(a[v][i], n - sz[v])] ++,
		ans[a[v][i]] += b[v][i];a[v].clear(), b[v].clear();
	}dfs2(rt, 0);
}
int main(){scanf("%d", &t);
	while (t --){scanf("%d", &n), G.init(n);
		for (int i = n - 1, u, v;i --;)
		scanf("%d%d", &u, &v), G.add2edge(u, v);memset(ans, 0, n + 1 << 3);
		al = n, mns = N, dfs(1, 0), dfs(rt, 0), solve(rt), ans[n] += n;
		for (int i = 1;i <= n;i ++) printf("%lld ", ans[i]);putchar('\n');
	}
}

You are given an array $$$a$$$. How to count the number of arrays $$$b$$$ that satisfy $$$f(b) = a$$$ and $$$ \forall 1 \le i \le n, b_i \le r_i $$$.?

You are given an array $$$a$$$. How to count the number of arrays $$$b$$$ that satisfy $$$f(f(b)) = a$$$ and $$$ \forall 1 \le i \le n, b_i \le r_i $$$.?

How many arrays $$$a$$$ satisfy there exists an array $$$b$$$ such that $$$f(f(b)) = a$$$?

The partition numbers.

// 全身全霊！MORE MORE JUMP!!
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#define mod 998244353
using namespace std;
typedef __int128_t lll;
template<typename T, const int M>
struct BHasher{inline int operator()(T x){return x % M;}};
template<typename T1, typename T2, int M, typename Hsr = BHasher<T1, M>>
struct HashMap{
	struct node{int nx;T1 ky;T2 vl;};
	int h[M];vector<node> nd;Hsr hsh;
	HashMap(){memset(h, -1, sizeof(h));}
	void clear(){memset(h, -1, sizeof(h)), nd.clear();}
	inline bool find(T1 k){int p = hsh(k);
		for (int i = h[p];i != -1;i = nd[i].nx)
		if (nd[i].ky == k) return 1;return 0;
	}
	inline T2& operator[](T1 k){int p = hsh(k);
		for (int i = h[p];i != -1;i = nd[i].nx)
		if (nd[i].ky == k) return nd[i].vl;
		nd.push_back((node){h[p], k, T2()});
		return nd[h[p] = nd.size() - 1].vl;
	}
};
const int N = 55, K = 1005, M = 1296000;HashMap<lll, int, 1919839> id;
int t, n, m, k, c, a[N], fa[M], to[M][N], C[N][N], f[M], ans[K], rt, cnt;
unsigned char b[M][N], bb[N], ps[M][N], sk[N], tmp[N], sm[M], ct[M], dep[M];
void dfs(int p, int sm){
	if (p > n){m ++;
		memcpy(ps[m], sk, sizeof(sk));
		memcpy(b[m], bb, sizeof(bb));
		return;
	}
	for (int x = 0;x <= n && sm <= n;x ++, sm += p){
		if (x) sk[++ c] = p;
		bb[p] = x, dfs(p + 1, sm);
		if (x) sk[c --] = 0;
	}
}
inline lll hsh(unsigned char* A){lll st = 0;
	for (int i = 1;i <= n;i ++)
	st <<= 1, st |= 1, st <<= A[i];return st;
}
inline unsigned char gdep(int x){return dep[x] ? dep[x] : dep[x] = gdep(fa[x]) + 1;}
inline void add(int& x, int y){x += y;if (x >= mod) x -= mod;}
int main(){scanf("%d", &t), n = N - 5;
	for (int i = 0;i <= n;i ++){C[i][0] = 1;
	for (int j = 1;j <= i;j ++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;}
	while (t --){scanf("%d%d", &n, &k), m = cnt = 0, dfs(1, 0);
		memset(dep, 0, m + 1 << 1), memset(f, 0, m + 1 << 2), memset(ans, 0, k + 1 << 2);
		for (int i = 1;i <= n;i ++) scanf("%d", &a[i]);
		for (int i = 1;i <= m;i ++){
			lll st = hsh(b[i]);id[st] = i;
			for (int j = n, p = -1;j >= 1;j --){
				p += b[i][j] + 1;if (b[i][j])
				to[i][j] = id[((st >> p) << p - 1) | (st & ((lll)1 << p) - 1)];
			}
		}
		for (int i = 1;i <= m;i ++){
			memset(tmp, 0, sizeof(tmp)), sm[i] = ct[i] = 0;
			for (int j = 1;j <= n;j ++)
			tmp[b[i][j]] ++, sm[i] += j * b[i][j], ct[i] += b[i][j];
			if (sm[i] == 1) rt = i;
			fa[i] = id[hsh(tmp)];
		}f[1] = dep[1] = dep[rt] = 1;
		for (int i = n, ss = 0;i >= 1;i --){
			for (int o = 1;o <= n;o ++) ss += a[o] == i;
			for (int j = m;j >= 1;j --)
			if (ct[j] <= n - i + 1 && sm[j] <= ss)
			for (int k = 1, x, now;ps[j][k];k ++)
			if (now = f[to[j][x = ps[j][k]]])
			f[j] = (f[j] + 1ll * now * C[ss - sm[j] + x][x]) % mod;
		}
		for (int i = 2;i <= m;i ++) add(ans[gdep(i) + 2], f[i]);
		for (int i = 1;i <= n;i ++) cnt += a[i] > 0;
		add(ans[3], mod - cnt), add(ans[2], cnt - (a[1] > 0)), add(ans[1], 1 + (a[1] > 0));
		for (int i = 1;i <= k;i ++) printf("%d ", ans[i]);putchar('\n');
	}
}

$$$a \oplus 1$$$ is equivalent to $$$a - 1$$$ when $$$a$$$ is an odd number, otherwise it is equivalent to $$$a + 1$$$.

If you apply $$$a \gets a \oplus 1$$$ when $$$a$$$ is odd, then that operation should make $$$a = b$$$.

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int t, a, b, x, y;
int main(){scanf("%d", &t);
	while (t --){scanf("%d%d%d%d", &a, &b, &x, &y);
		if (a > b) printf("%d\n", (a ^ 1) == b ? y : -1);
		else {int c0 = b - a, c1 = (b + 1 >> 1) - (a + 1 >> 1);
		printf("%lld\n", y > x ? 1ll * c0 * x : 1ll * (c0 - c1) * x + 1ll * c1 * y);}
	}
}

Transform $$$(p_x,p_y)$$$ to $$$(q_x,q_y)$$$ into an operation where $$$a_i$$$ is the distance between the two points.

When $$$n+1=3$$$, there is a solution if and only if the largest $$$a_i$$$ is less than or equal to the sum of the remaining $$$a_i$$$.

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 100010
#define int long long
int t,n,sx,sy,tx,ty;
double a[N];
signed main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		cin>>sx>>sy>>tx>>ty;
		for(int i=1;i<=n;i++)
		 cin>>a[i];
		a[++n]=sqrt((sx-tx)*(sx-tx)+(sy-ty)*(sy-ty));
		sort(a+1,a+n+1);
		double sum=a[n];
		for(int i=1;i<n;i++)
		 sum-=a[i];
		if(sum<=0)
		 puts("Yes");
		else
		 puts("No");
	}
}

#include<iostream>
#include<algorithm>
using namespace std;
#define N 100010
#define int long long
int t,n,sx,sy,tx,ty,a[N];
signed main()
{
	cin>>t;
	while(t--)
	{
		cin>>n;
		cin>>sx>>sy>>tx>>ty;
		for(int i=1;i<=n;i++)
		 cin>>a[i];
		sort(a+1,a+n+1);
		int p=(sx-tx)*(sx-tx)+(sy-ty)*(sy-ty);
		if(p>a[n]*a[n])
		{
			int sum=0;
			for(int i=1;i<=n;i++)
			{
				sum+=a[i];
				if(sum*sum>=p)
				 break;
			}
			if(sum*sum>=p)
			 puts("Yes");
			else
			 puts("No");
		}
		else
		{
			int sum=a[n];
			for(int i=1;i<=n-1;i++)
			 sum-=a[i];
			if(sum<=0||sum*sum<=p)
			 puts("Yes");
			else
			 puts("No");
		}
	}
}

For odd $$$n$$$, setting $$$a_i = l$$$ for all $$$i$$$ suffices.

For even $$$n$$$, there does not exist a valid array $$$a$$$ that satisfies $$$a_1=a_2=\dots=a_{n-1}=l$$$.

For even $$$n$$$, try to make $$$a_1=a_2=\dots=a_{n-2}=l$$$.

#include<iostream>
using namespace std;
#define int long long
int t,n,l,r,k;
signed main()
{
	cin>>t;
	while(t--)
	{
		cin>>n>>l>>r>>k;
		if(n%2==1)
		{
			cout<<l<<endl;
			continue;
		}
		if(n==2)
		{
			cout<<-1<<endl;
			continue;
		}
		int res=1;
		bool fl=0;
		while(res<=r)
		{
			if(res>l)
			{
				fl=1;
				if(k<=n-2)
				 cout<<l<<endl;
				else
				 cout<<res<<endl;
				break;
			}
			res*=2;
		}
		if(!fl)
		 cout<<-1<<endl;
	}
}

Calculating the weight of a single valid sequence is difficult. Try another way?

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int N = 5005;
int t, n, mod, f[N][N], ans;
inline void add(int& x, int y){x += y;if (x >= mod) x -= mod;}
int main(){scanf("%d", &t);
	while (t --){scanf("%d%d", &n, &mod), f[0][0] = 1, ans = 0;
		for (int i = 1;i <= n;i ++) for (int j = 0;j <= i;j ++) f[i][j] = 0;
		for (int i = 1;i <= n;i ++)
		for (int j = 0, now;j < i;j ++)
		if (now = f[i - 1][j]) add(f[i][j + 1], now),
		f[i][j] = (f[i][j] + (n - i + 1ll) * (j + 1) * now) % mod;
		for (int j = 0;j <= n;j ++) add(ans, f[n][j]);printf("%d\n", ans);
	}
}

As same as the title, can you find a simple necessary constraint?

Consider $$$a_i = 0$$$ first.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
struct stu{
	int x;
	ll dp;
};
int n,a[100007],b[100007];
vector<stu> f,g;
const ll inf=0x3f3f3f3f3f3f3f3f;
void Subt(){
	cin>>n;
	for(int i=1;i<n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	a[n]=0;
	f.clear();
	f.push_back((stu){0,0});
	for(int i=1;i<=n;i++){
		int x=0;
		g.clear();
		for(int j=30;j>=-1;j--){
			int y=x|a[i-1]|a[i];
			if(j!=-1) y|=(1<<j); 
			if(y>=b[i]){
				ll mn=inf;
				for(stu l:f){
					if((l.x&y)!=a[i-1]) continue;
					mn=min(mn,l.dp+y-b[i]);
				}
				if(mn<inf) g.push_back((stu){y,mn});
			}
			x|=((1<<j)&b[i]);
		}
		swap(f,g);
	}
	ll mn=inf;
	for(stu l:f) mn=min(mn,l.dp);
	if(mn<inf) cout<<mn<<endl;
	else cout<<-1<<endl;
	return;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T=1;
	cin>>T;
	while(T--) Subt();
}

Try to determine the vertex where you were before the last move.

I just need to calculate the earliest time I can reach the end vertex.

What form of moving path from the starting vertex to the end vertex is considered optimal?

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
#include<queue>
#include<unordered_map>
#include<map>
#define int long long
using namespace std;
int n,st,dist[1000002],w[1000001],tim[1000001],ans;
vector <int> g[1000001];
int f[1000001];
queue<int> q;
void getdis(int u,int fa)
{
	for(int v:g[u])
	{
		if(v==fa) continue;
		dist[v]=dist[u]+1;
		getdis(v,u);
	}
}
void dfs(int u,int fa,int k,bool inn,int hei,int TIM,int dis)
{
	if(hei<0)
	{
		TIM=max(TIM,(-hei+1)/2*2+k*2+dis);
	}
	if(TIM<=dist[u])
	{
		ans=max(ans,dist[u]);
	}
	else
	{
		return;
	}
	for(int v:g[u])
	{
		if(v==fa) continue;
		if(inn&&w[u]!=w[v])
		{
			dfs(v,u,min(k,tim[v]),inn,hei+w[v],TIM+1,dis+1);
		}
		else
		{
			dfs(v,u,k,0,hei+w[v],TIM+1,dis+1);
		}
	}
}
int T; 
signed main()
{
	ios::sync_with_stdio(false);
	cin>>T;
	int cnt=0;
	while(T--)
	{
		cnt++;
		cin>>n>>st;
		for(int i=1;i<=n;i++)
		{
			dist[i]=0;
			tim[i]=1000000000;
			g[i].clear();
			f[i]=-10000000000000000;
		}
		ans=0;
		for(int i=1;i<=n;i++)
		{
			cin>>w[i];
		}
		for(int i=1,u,v;i<n;i++)
		{
			cin>>u>>v;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		getdis(1,-1);
		for(int i=1;i<=n;i++)
		{
			for(int v:g[i])
			{
				if(w[i]==1&&w[v]==1)
				{
					tim[i]=0;
					q.push(i);
					break;
				}
			}
		}
		while(!q.empty())
		{
			int u=q.front();
			q.pop();
			for(int v:g[u])
			{
				if(tim[v]==1000000000&&w[v]!=w[u])
				{
					tim[v]=tim[u]+1;
					q.push(v);
				}
			}
		}
		dfs(st,-1,tim[st],1,w[st],1,1);
		cout<<ans+(dist[st]&1)-1<<'\n';
	}
}