Luogu Simu9 T2

题目描述

有间屋子，由条双向道路连接成了一个树形结构。其中，第间屋子里居住了个种族为的人。

现在你要召集一个连通块内的人。设表示被召集的种族为的人个数，若存在，则种族为的人会造反。

你想知道有多少个连通块会使某种人造反，答案对取模。

输入格式

第一行一个正整数。

第二行个整数。

接下来行，每行两个整数，表示有一条边连接第间和第间屋子。

输出格式

一行一个整数，表示答案。

15
5 13 5 1 13 5 14 6 14 12 8 1 12 14 5
2 1
7 1
8 4
10 3
15 1
1 9
1 6
13 1
5 2
14 15
3 9
1 4
3 12
10 11

提示

** 样例解释 1**

共个连通块，仅不引起造反。

样例解释 2

除去大小为的连通块，还有引起造反。

数据范围

对于数据，。

对于另外数据，树为的链。

对于另外的数据，。

对于的数据，，。

我们只关注众数，对于区间众数，我们有非常经典的分治做法

一个众数要打赢原本的众数必然需要，也就是每产生一个众数翻倍，所以，的众数都只有种，而绝对众数必然是小区间的绝对众数中的一个，反证法显然

所以我们对这个众数，每次操作区间，和它相同的变成，不同变成，问题转化为求，直接桶维护，

总复杂度

int solve(int l,int r)
{
    if(l==r) return 1;
    int mid=(l+r)>>1;
    int res=solve(l,mid)+solve(mid+1,r);
    
    vector<int> vec(0);
    for(int i=mid;i>=l;i--)
    {
        cnt[a[i]]++;
        if(2*cnt[a[i]]>(mid-i+1)) vec.pb(a[i]);
    }
    for(int i=mid;i>=l;i--) cnt[a[i]]--;
    for(int i=mid+1;i<=r;i++)
    {
        cnt[a[i]]++;
        if(2*cnt[a[i]]>(i-mid)) vec.pb(a[i]);
    }
    for(int i=mid+1;i<=r;i++) cnt[a[i]]--;

    for(auto v:vec)
    {
        if(vis[v]) continue;
        vis[v]=1;
        for(int i=l;i<=r;i++) b[i]=(a[i]==v)?1:-1;
        s[mid]=b[mid],s[mid+1]=b[mid+1];
        for(int i=mid-1;i>=l;i--)
            s[i]=s[i+1]+b[i];
        for(int i=mid+2;i<=r;i++)
            s[i]=s[i-1]+b[i];
        int len=mid-l+1;
        for(int i=l;i<=mid;i++) cnt[s[i]+len]++;
        for(int i=len*2-1;~i;i--) cnt[i]+=cnt[i+1];
        for(int i=mid+1;i<=r;i++)
            res+=cnt[1-s[i]+len];
        for(int i=0;i<=len*2;i++) cnt[i]=0;
    }
    for(auto v:vec) vis[v]=0;
    return res;
}

我们把这个玩意上树，还是相同设为，不同设为，我们直接枚举作为众数，，然后做树形

设表示内所有连通块，众数个数为的方案数

转移时维护，就是 min(sz[x],-cnt) 和 max(sz[x],cnt)，然后做背包即可，这样复杂度均摊是的，但是我不会证，但是可能不会超过，按根号考虑即可

#include<bits/stdc++.h>
#define int long long
#define pt putchar(' ')
#define nl puts("")
#define pi pair<int,int>
#define pb push_back
#define go(it) for(auto &it:as[x])
using namespace std;

const int N=3e3+10,Q=998244353;
int n,u,v,cnt,ans;
int a[N],c[N],sz[N],f[N][N*3],ct[N],L[N],R[N];
vector<int> as[N];

int fr(){
    int x=0,flag=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') flag=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x*flag;
}
void fw(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) fw(x/10);
    putchar(x%10+'0');
}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void mod(int &x,int y){if((x+=y)>=Q) x-=Q;}

void dfs(int x,int rt)
{
    sz[x]=1;
    f[x][c[x]+N]=1;
    int g[N<<1];
    go(v)
    {
        if(v==rt) continue;
        dfs(v,x);
        int vr=min(sz[x],cnt),vl=max(-sz[x],-cnt);
        int svr=min(sz[v],cnt),svl=max(-sz[v],-cnt);
        for(int j=vr;j>=vl;j--) g[j+N]=f[x][j+N];
        for(int j=vr;j>=vl;j--)
            for(int k=svr;k>=svl;k--)
                if(j+k>=-cnt) mod(f[x][j+k+N],g[j+N]*f[v][k+N]%Q);
        sz[x]+=sz[v];
    }
    for(int j=1;j<=min(cnt,sz[x]);j++)
        mod(ans,f[x][j+N]);
    L[x]=max(-sz[x],-cnt),R[x]=min(sz[x],cnt);
}

signed main()
{
    n=fr();
    for(int i=1;i<=n;i++) ct[a[i]=fr()]++;
    for(int i=1;i<n;i++)
    {
        u=fr(),v=fr();
        as[u].pb(v),as[v].pb(u);
    }

    for(int i=1;i<=n;i++)
    {
        cnt=ct[i];
        if(!cnt) continue;
        else if(cnt==1) ans++;
        else
        {
            for(int x=1;x<=n;x++)
                for(int j=L[x];j<=R[x];j++)
                    f[x][j+N]=0;
            for(int x=1;x<=n;x++)
                c[x]=(a[x]==i)?1:-1;
            dfs(1,-1);
        }
    }
    fw(ans);
    return 0;
}