2024蓝桥杯弱鸡ca组参赛记录……

• A 3228 就模拟，但是代码敲了20多分钟，废死了时间

• B 没写，因为第一题的代码敲得太久，看着此题暴力枚举更复杂，加之考前做填空题几乎没对过……

• C 想不到正解，遂暴力，枚举共同训练的次数，应该拿部分分

• D 不知道是否正解，建树，之后二分深度，对于每个深度，都由预先dfs出的每层的set检测是否存在前缀

• E 不会，直接cout<<-1<<endl…

但是赛后思考了下，好像是败给了数学? 二分，之后方差的公式化为$\sum x^2-\overline{x}^2$，之后显然排序一下，再从小到大枚举就行了。。。 不知道对不对，还没验证

• F 又不会，又是暴力的$o(n^4)$

• G 发现了是个树，也看见了c的范围，所以就用的倍增lca+枚举20个种类，希望没有翻车，拿下这20分

• H 不会……

如果一切顺利，35分左右的样子？
感觉省一无了QAQ

放个考场上写的G题的代码吧，也求佬看见了帮忙查一查，希望没问题
QAQ

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<utility>
#include<vector>
#include<unordered_set>
#define inf 0x3f3f3f3f
#define endl '\n'
#define fi first
#define se second
#define sz(a)  (int)a.size()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int N = 1e5+10,M=1e5+10,C=20+5;
int n,q;
int c[N];
int h[N],ne[2*N],e[2*N],idx;
int f[N][22],dep[N];
int cnt[N][C]; 
void add(int a,int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void dfs(int u,int fa)
{
    dep[u] = dep[fa]+1;
    f[u][0] = fa;
    for(int i=1;i<=20;i++)
    {
        f[u][i] = f[f[u][i-1]][i-1];
    }
    for(int i=h[u];i!=-1;i=ne[i])
    {
        if(e[i]!=fa)
        {
            dfs(e[i],u);
        }
    }
}
int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);

    // tongyiceng
    for(int i=20;i>=0;i--)
    {
        if(dep[f[x][i]]>=dep[y])
            x = f[x][i];
    }

    if(x==y) return x;
    // lca xiayiceng
    for(int i=20;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
            x = f[x][i],y = f[y][i];
    }
    return f[x][0];
}
void dfs_num(int x,int cc,int fa)
{

    cnt[x][cc] = cnt[fa][cc];
    if(c[x]==cc)
        cnt[x][cc]++;
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int j = e[i];
        if(fa!=j)
            dfs_num(j,cc,x);
    }   
}
void solve()
{
    // coding here!
    memset(h,-1,sizeof h);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=n-1;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1,0);  //建树！


    for(int i=1;i<C;i++)
    {
        dfs_num(1,i,0);
    }

    while(q--)
    {
        int s,t;
        cin>>s>>t;
        int p = lca(s,t);
        p=f[p][0];
//      cout<<s<<' '<<t<<' '<<p<<"====="<<endl;
        // 维护  s-lca-t 两条路上的c的数量
        int ans=0;
        for(int i=1;i<=20;i++)
        {
            if(cnt[s][i]+cnt[t][i]-2*cnt[p][i]>0)
                ans++;
        }
        cout<<ans<<endl;
    }



//6 1
//1 2 3 1 2 3
//1 2
//1 3
//2 4
//2 5
//3 6


//5 4

//4 3
//1 4
//2 3

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