首页 > 其他分享 >CF 杂题集1 2200~2400

CF 杂题集1 2200~2400

时间：2023-11-04 16:44:22浏览次数：37  
标签：2200 sz head const int void CF 集合 杂题

upd on 2023.11.02 初稿
upd on 2023.11.04 修正部分表达

感觉这一套题质量都很不错，有比较好的思维难度，又不是特别难（当然，对于我来说很难），而且有一些比较好的思路和套路。

题目链接均为洛谷链接。

CF1474D Cleaning

摘要：

  1. 性质：考虑端点，发现一定可以从左右两侧开始消除。

  2. 分别维护单独从一侧消除的相关信息。

  3. 枚举交界处，检查是否有解。

分析性质：

因为“使用交换”后会变成“不使用交换”的情况，所以先分析不使用/交换后的情况。因为在两端的数至多有一种消除方法，所以若有解，一定存在消除方案，满足每次消除最外侧，从左右两端向中间交界消除，形如 \(a_1 \rightarrow a_i,a_{i+1} \leftarrow a_n\)。

进一步考虑交换。若交换的位置单独包含于某一侧，则相当于没有产生影响，所以交换的位置应当是从左右两边开始消除的交界。如果能枚举交换位置并直接判断是否可行，问题就解决了。

实现：

于是，考虑对于两个方向分别维护：如果强行消除这个数之前的所有数，这个数剩了多少，记为 \(resl_i,resr_i\)（如果是负的说明已经不可行），以及两方向最多消除到哪里。

接着枚举两方向的交界，检查是否有解，设为 \(a_i,a_{i+1}\)。有两种合法情况：若不使用能力，则应有 \(a_i-res_{i-1} = a_{i+1}-res_{i+2} \ge 0\)；若使用，则应有 \(a_{i+1}-res_{i-1} = a_{i}-res_{i+2}\ge 0\)。

AC Link

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

const int N=2e5+10;
int n,a[N],l,r;
int ansl[N],ansr[N];
void work()
{
    #define YES return puts("YES"),void()
    #define NO return puts("NO"),void()
    scanf("%d",&n);l=0,r=n+1;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        ansl[i]=ansr[i]=a[i];
    ansl[0]=ansr[n+1]=0;
    for(int i=1;i<=n;i++)
    {
        ansl[i+1]-=ansl[i];l=i;
        if(ansl[i+1]<0)break;
    }
    for(int i=n;i>=1;i--)
    {
        ansr[i-1]-=ansr[i];r=i;
        if(ansr[i-1]<0)break;
    }
    if(ansl[n]==0||ansr[1]==0)YES;
    // printf("l=%d,r=%d\n",l,r);
    // for(int i=1;i<=n;i++)
    //     printf("%d ",ansl[i]);puts("");
    // for(int i=1;i<=n;i++)
    //     printf("%d ",ansr[i]);puts("");
    for(int i=1;i<n;i++)//swap_it ; 1~n-1
    {
        if (i-1>l || i+2<r)continue;
        if
        (
            (
                ( (a[i]-ansl[i-1]) >= 0 )
            &&  ( (a[i]-ansl[i-1]) == (a[i+1]-ansr[i+2]) )
            )
            ||
            (
                ( (a[i+1]-ansl[i-1]) >= 0 )
            &&  ( (a[i+1]-ansl[i-1]) == (a[i]-ansr[i+2]) )
            )
        )YES;
    }
    NO;
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)work();
}

CF1468A LaIS

摘要：

  1. DP。

  2. 性质：选出上升子序列，并加入（若有）不会成为 \(min\) 的数。

  3. 由性质设计 DP 状态，并用贪心优化转移策略。

  4. 单调栈维护最近更大值，树状数组维护最大最远转移点。

首先分析合法序列的性质：

对于 \(b_1,b_2,b_3\)，最小值在 \(b_1\) 或 \(b_2\)。

分别考虑两种情况并拓展，发现每次向\(b_1,...,b_{i-1},b_i\) 中加入 \(b_{i+1}\) 时，\(b_{i+1} \ge \min(b_{i-1},b_i)\)，序列整体似乎呈上升趋势。

进一步地，发现合法序列可以拆分成两部分。第一部分为某个不降序列，第二部分中，每个元素两侧的元素均属于第一部分（此元素处于序列首时例外）。

接下来推导 DP 状态及转移：

设 \(f_i\) 表示不降序列以 \(i\) 结尾时，合法序列的最长长度。于是有转移

\[f_i=\max_{j<i,a_j < a_i}{(f_j+[\exists k \in [j+1,i-1],a_k>a_i ])}; \]

发现由于 \(k\) 至多带来 \(1\) 的贡献，那么为了 \(k\) 而选择更小的 \(j\) 是不优的，应优先保证 \(f_j\) 最大。在此基础上，为了使更可能存在合法的 \(k\)，需要使下标 \(j\) 最小，并检查这一段区间的最大值是否大于 \(a_i\)。

最后是转移的实现：

发现加入 \(k\) 只有一次，所以可以转化为：（在 \(i\) 之前）最近的大于 \(a_i\) 的数的下标是否大于 \(j\)，可以采用单调栈维护。

发现 \(j<i,a_j<a_i\) 是一个二维偏序问题，考虑在意义上将 \(j,f_j\) 打包，放在下标为 \(a_j\) 的位置，每次树状数组查询 \(a_i\) 的前缀最优（即 \(f_j\) 更大或 \(f_j\) 相同时 \(j\) 更小）。

AC Link

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

const int N=5e5+10;
int n,a[N],dp[N];
struct node{int val,pos;};
node w[N];
#define lowbit(x) (x)&(-(x))
void trans(node &x,node &y)
{
    if  ( (x.val<y.val) || (x.val==y.val&&x.pos>y.pos) )x=y;
}
void update(int x,node k)
{
    while(x<=n)
        trans(w[x],k),x+=lowbit(x);
}
node query(int x)
{
    node res={0,0};
    while(x)
        trans(res,w[x]),x-=lowbit(x);
    return res;
}
int sta[N],tp,lst[N];
void work()
{
    int ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        while(tp&&a[i]>=a[sta[tp]])tp--;
        lst[i]=sta[tp],sta[++tp]=i;
    }
    for(int i=1;i<=n;i++)
    {
        node tmp=query(a[i]);
        dp[i]=tmp.val+1;
        if(lst[i]>tmp.pos)dp[i]++;
        ans=max(ans,dp[i]);

        node now={dp[i],i};
        update(a[i],now);
    }
    printf("%d\n",ans);
}
void clear()
{
    for(int i=1;i<=n;i++)
        w[i]={0,0},lst[i]=dp[i]=0;
    tp=0;
}

int main()
{
    int T;scanf("%d",&T);
    while(T--)
        work(),clear();
    return 0;
}

CF1476E Pattern Matching

摘要：

  1. 性质：给出要求等价于顺序限制。

  2. 性质：\(k \le 4\)，枚举通配符，得到所有可匹配模式串。

  3. 建边，拓扑排序。

每个要求实际上限制了指定串的位置先于其它可匹配模式串。

由于 \(k \le 4\)，可以对于每个匹配串 \(m_i\) 枚举所有通配符出现情况，并查看是否有相同模式串。当然，也可以对模式串枚举，这样会有常数级优化，但相对不好写。

然后对于每一个匹配串 \(m\)，设指定模式串为 \(t\)，未指定但可匹配的串的集合为 \(S\)，\(pos_x\) 表示模式串 \(x\) 的排序后位置，则有 $\forall pos_{t} < pos_{S_i} $，于是 \(t\) 向 \(S_i\) 连边，表示 \(S_i\) 应排在 \(t\) 之后，拓扑排序求解。

碎碎念：
其实一开始想写成 \(pos_t < \min_{x\in S} pos_x\)，然而发现不利于思路通顺改掉了。回头一想，发现这一类 min/max 关系似乎也可能转拓扑，可能是个没什么用的 Trick。

AC Link

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

const int N=1e5+10;
const int V=N,E=N*16;

struct edge{int to,nxt;};
edge e[E*2];int head[V],tot;
void add(int u,int v)
{
    e[++tot]={v,head[u]};head[u]=tot;
}

int n,m,k,limk,mt[N],id[531441+100];
char p[N][6],s[N][6];
int Hash(char *s)
{
    int res=0;
    for(int i=1;i<=k;i++)
        res*=27,res+=(s[i]=='_')?0:s[i]-'a'+1;
    return res;
}
int ans[N],cnt,indeg[N];queue<int>q;
void Push(int x){q.push(x),ans[++cnt]=x;}
bool topo()
{
    int vis=0;
    for(int i=1;i<=n;i++)
        if(!indeg[i])Push(i);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(!(--indeg[v]))Push(v);
        }
    }
    return cnt==n;
}
bool check(char *pp,char *ss)
{
    for(int i=1;i<=k;i++)
        if(pp[i]!='_'&&ss[i]!=pp[i])return false;
    return true;
}
void debug()
{
    return ;
    for(int i=1;i<=n;i++)
    {
        cout<<Hash(p[i])<<" ";
    }cout<<endl;
    for(int i=1;i<=m;i++)
    {
        cout<<Hash(s[i])<<" ";
    }cout<<endl;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);limk=(1<<k)-1;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",p[i]+1);
        id[Hash(p[i])]=i;
    }
    char tmp[6];
    for(int i=1;i<=m;i++)
    {
        scanf("%s",s[i]+1);
        scanf("%d",&mt[i]);
        if(!check(p[mt[i]],s[i]))return puts("NO"),0;
        int u=Hash(p[mt[i]]),w=Hash(s[i]);
        for(int j=0;j<=limk;j++)
        {
            bitset<4>b=j;
            for(int l=1;l<=k;l++)
            {
                if(j&(1<<(l-1)))
                    tmp[l]='_';
                else 
                    tmp[l]=s[i][l];
            }
            int v=Hash(tmp);
            if(u==v||id[v]==0)continue;
            add(id[u],id[v]);indeg[id[v]]++;
        }
    }
    if(topo())
    {
        puts("YES");
        for(int i=1;i<=cnt;i++)
            printf("%d ",ans[i]);puts("");
    }
    else 
    {
        puts("NO");
    }
    return 0;
}

CF1467D Sum of Paths

摘要：

  1. 单点点权修改，答案变化量取决于该点被到达的次数。

  2. 由只走 \(i\) 步到 \(j\) 的方案数算出在第 \(i\) 步到 \(j\) 的方案数，加和即所求。

如果我们可以求出每个点被走了多少次，那么就可以 \(O(1)\) 地修改了。

每次走一步题、求方案数题、\(n^2\) 可过题，那大概率会有个很典的东西：设 \(f_{i,j}\) 表示走了 \(i\) 步，当前走到 \(j\) 的方案数。转移显然：

\[ f_{i,j}=f_{i-1,j-1}+f(i-1,j+1) \]

然而打表出来发现不太对，因为 \(f_{i,j}\) 只计算到 第 \(i\) 步，后面的没有算。

怎么办呢？发现其实走后面的 \(n-i\) 步可以看成从某个点为终点，倒着走 \(n-i\) 步到 \(j\)，与正着走 \(n-i\) 步 到 \(j\) 没有任何不同，于是可以“拼接”。

所以考虑设 \(g_{i,j}\) 表示走满步数，在第 \(i\) 步走到 \(j\) 的方案数，转移：

\[ g_{i,j}=f_{i,j} \times f_{k-i,j} \]

对于每个点 \(j\)，累加所有的 \(g_{i,j}\)，得到所有方案中被走到的次数 \(sum_j\)，那么每次答案的改变量就是 \(sum_j \times (val^{'}_j-valj)\)。

也许有的同学怀疑前后“拼接”的方式会算重，比如从 \(a\) 到 \(b\) 再到 \(a\) 被算了两次或多次。实际上不会，因为从逻辑上讲，\(b\) 到 \(a\) 时间上在 \(a\) 到 \(b\) 之后，两者是完全分开，互不影响的。

AC Link

Code 
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5010,mod=1e9+7;
int n,k,q,a[N];
int f[N][N],g[N][N],sum[N];
void init()
{
    for(int j=1;j<=n;j++)
        f[0][j]=1;
    for(int i=1;i<=k;i++)
        for(int j=1;j<=n;j++)
            f[i][j]=(f[i-1][j-1]+f[i-1][j+1])%mod;
    for(int j=1;j<=n;j++)
        for(int i=0;i<=k;i++)
            g[i][j]=1ll*f[i][j]*f[k-i][j]%mod;
    for(int j=1;j<=n;j++)
        for(int i=0;i<=k;i++)
            sum[j]=(sum[j]+g[i][j])%mod;
}
LL ans[N];int cnt;
signed main()
{
    scanf("%d%d%d",&n,&k,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    init();
    LL now=0;
    for(int i=1;i<=n;i++)
    {
        now=(now+1ll*sum[i]*a[i]%mod)%mod;
    }
    for(int i=1;i<=q;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        now = (now+(1ll*(y-a[x])*sum[x]%mod))%mod;
        now = (now+mod)%mod;
        a[x]=y;
        ans[++cnt]=now;
    }
    for(int i=1;i<=q;i++)
        printf("%lld\n",ans[i]);
    return 0;
}

CF1468M Similar Sets

摘要：

  1. 根号分治

  2. 对每个大集合遍历所有集合，桶处理。

  3. 对所有小集合枚举所有元素对，按较小值放入容器，每个容器桶处理。

  4. 注意算空间调块长，注意离散化，注意清空。

  5. 存在二分图做法，但个人觉得没必要。

根号分治的根本在于总大小有保障。对于本题，发现从元素入手不一定好处理，于是从集合入手。以下设块长为 \(B\),大小大于 \(B\) 的称作大集合，其余为小集合。

大集合数量不超过 \(B\) 级别，所以支持对每个大集合进行全局遍历。对于每个大集合，同其它所有集合比对，用桶维护大集合每个元素是否出现，如果比对时有不少于两次发现存在相同元素则得解。

小集合大小不超过 \(B\)。设小集合数量为 \(k\)，则 \(kB \le n\)，而 \(kB^2 \le Bn\)，所以支持对每个小集合进行平方级别处理。考虑枚举所有元素对，类似 stl map 的思路，按小值为键，大值、编号为值，放入对应容器中。遍历每个容器，如果遇到新元素将桶中放入集合编号，遇到第二次得解。

tag 里有一个“graphs”的标签，是说将集合与元素的关系视作二分图，然后在两集合中存在相同元素对转化为找四元环，但是个人感觉没有什么本质区别，反而绕来绕去显得麻烦。

AC Link

Code 
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mkp(x,y) make_pair((x),(y))
#define fir first
#define sec second
const int N=1e5+10;
int n,B;
vector<int>s[N];
int buc[N*2];
vector<pii>p[N*2];
int brr[N*2],len;
void work()
{
    scanf("%d",&n);B=0;len=0;
    for(int i=1;i<=n;i++)
    {
        int j;scanf("%d",&j);
        B+=j;
        while(j--)
        {
            int x;scanf("%d",&x);
            s[i].push_back(x);brr[++len]=x;
        }
    }
    B=sqrt(B)/2;
    sort(brr+1,brr+len+1);len=unique(brr+1,brr+len+1)-brr-1;
    for(int i=1;i<=n;i++)
    {
        for(auto &x:s[i])
            x=lower_bound(brr+1,brr+len+1,x)-brr;
    }
    pii ans=mkp(0,0);
    for(int i=1;i<=n;i++)
    {
        if((int)s[i].size()<=B)continue;
        for(auto x:s[i])buc[x]=1;
        for(int j=1;j<=n;j++)
        {
            if(j==i)continue;
            bool cnt=0;
            for(auto y:s[j])
            {
                if(buc[y])
                    cnt?ans=mkp(i,j),1:cnt=1;
            }
        }
        for(auto x:s[i])buc[x]=0;
        if(ans.fir)return printf("%d %d\n",ans.fir,ans.sec),void();
    }
    for(int i=1;i<=n;i++)
    {
        if((int)s[i].size()>B)continue;
        for(int j=0;j<s[i].size();j++)
        {
            for(int k=j+1;k<s[i].size();k++)
            {
                p[min(s[i][j],s[i][k])].push_back(mkp(max(s[i][k],s[i][j]),i));
            }
        }
    }
    for(int i=1;i<=len;i++)
    {
        for(auto x:p[i])
            buc[x.fir]?ans=mkp(buc[x.fir],x.sec),1:buc[x.fir]=x.second;
        for(auto x:p[i])
            buc[x.fir]=0;
        if(ans.fir)return printf("%d %d\n",ans.fir,ans.sec),void();
    }
    return puts("-1"),void();
}
void clear()
{
    for(int i=1;i<=n;i++)
        s[i].clear();
    for(int i=1;i<=len;i++)
        p[i].clear();
}

int main()
{
    int T;scanf("%d",&T);
    while(T--)work(),clear();
    return 0;
}

CF1528C Trees of Tranquillity

摘要：

  1. 性质：第一棵树上选一条从上到下的链上的结点。

  2. 转化：第二棵树不存在祖先关系等价于入栈出栈时间无交（无嵌套）。

  3. 贪心：若存在嵌套，取小区间不劣。

  4. 实现：在第一棵中 dfs，依据贪心策略加入、弹出；记录操作，回溯时撤销。

  5. 实现：用 set 存储点，依据入栈出栈序性质判断区间关系。

本题的两个核心分别是：入栈出栈序性质的使用、使用 set 维护两两不交或嵌套区间。以下所有“入栈出栈”相关均指第二棵树，并用 \(in,out\) 分别表示入栈出栈时间，也即两者构成的区间的端点。

首先，两两存在祖先关系一定对应了一条链。于是我们可以在第一棵树上 dfs 了，接下来要处理第二棵树。

由于 dfs 入栈出栈序的性质，如果存在祖先关系，则祖先的入栈出栈区间包含后代的区间。考虑贪心，如果两个区间出现冲突，选小的区间一定是不劣的。

如何维护区间呢？请使用 stl set。有大佬手写红黑树我没有任何意见。

在 set 中，我们将点按 \(in\) 排序。判断区间 \(u\) 内是否有区间的方式是，lower_bound 找到第一个 \(v\) 使得 \(in_v\) 大于 \(in_u\) ，查看 \(out_v\) 是否在 \(out_u\) 之前；而判断是否被包括的方式是，lower_bound \(u\) 后将指针 it--，查看前一个元素的信息并依样判断。

需要注意，如果不存在想找的元素，指针会返回 set.begin 和 set.end，注意特判。另外，由于我们时刻保证区间无交，两种判断一次即可，但对于更加一般的问题可能包含多个或被多个包含，具体问题具体分析。

AC Link

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

const int N=3e5+10;
struct edge{int to,nxt;};
edge e[N];int head[N],tot;
int in[N],out[N],cnt;
vector<int>ee[N];
int n,ans;
set< pair<int,int> >s;
vector< pair<int,char> >opt[N];
#define Pair(_) (make_pair(in[(_)],(_)))
void add(int u,int v)
{
    e[++tot]={v,head[u]};head[u]=tot;
}
void dfs0(int u,int pa)
{
    in[u]=++cnt;
    for(auto v:ee[u])
        dfs0(v,u);
    out[u]=++cnt;
}
int check(int u)// 0 -> 可以加入；-1 -> 不可加入；x -> 需要删去 x
{
    auto it=s.lower_bound(Pair(u));
    if(it!=s.end()&&out[it->second]<out[u])
        return -1;
    if(it==s.begin())
        return 0;
    it--;
    if(out[it->second]<in[u])return 0;
    if(out[it->second]>out[u])return it->second;
    return -2;
}
void dfs1(int u,int pa)
{
    int flag=check(u);
    if(flag>=0)
    {
        s.insert(Pair(u)),
        opt[u].push_back(make_pair(u,'A'));
        if(flag>0)
            s.erase(Pair(flag)),
            opt[u].push_back(make_pair(flag,'D'));
    }
    ans=max(ans,(int)s.size());
    for(int i=head[u];i;i=e[i].nxt)
    {
        dfs1(e[i].to,u);
    }
    for(auto v:opt[u])
    {
        if(v.second=='A')//之前 Add
            s.erase(Pair(v.first));
        else if(v.second=='D')//之前 Delete
            s.insert(Pair(v.first));
    }
    opt[u].clear();
}
void clear()
{
    for(int i=1;i<=n;i++)
        in[i]=out[i]=head[i]=0,ee[i].clear();
    tot=cnt=0;
    s.clear();
    ans=0;
}
void work()
{
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        int u;scanf("%d",&u);
        add(u,i);
    }
    for(int i=2;i<=n;i++)
    {
        int u;scanf("%d",&u);
        ee[u].push_back(i);
    }
    dfs0(1,0);
    for(int i=head[1];i;i=e[i].nxt)
    {
        dfs1(e[i].to,0);
    }
    printf("%d\n",ans);
}

int main()
{
    int T;scanf("%d",&T);
    while(T--)
        work(),clear();
    return 0;
}

CF1485F Copy or Prefix Sum

摘要：

  1. 从值域入手设计 DP 状态。

  2. 分析 DP 的性质，采用数据结构维护并转移。

  3. 本题卡哈希，请使用 map 保证复杂度。

这题似乎不太能从第几个、选什么来 DP，依据 \(b\) 数组的相互关系也不太可做，不得不从值域入手，然而值域 \(10^9\)。先试试吧，万一有惊喜呢？DP 题只想出暴力肯定要挖掘一下啊。

设 \(f_{i,j}\) 表示符合了 \(b_1\) 到 \(b_i\) 的限制，\(\sum a_x = j\) 的方案数，转移如下：

\[\begin{cases} f_{i,j} \leftarrow f_{i-1,j-b_i} &b_i=a_i\\ f_{i,b_i} \leftarrow \sum f_{i,k} &b_i=\sum a_x\\ \end{cases} \]

发现我们似乎不需要真的遍历值域，同时存储 \(i\) 这一维是无用的。状态改为\(f_j\)。第一个转移相当于全局平移，只需要记录 \(\Delta j\)，表示已经平移了多少，每次将 \(\Delta j\) 加上 \(b_i\)，访问时由 \(j\) 变为 \(j-\Delta j\)。对于第二个转移，记录全局 \(sum\) 可以解决。

那么如何存储 \(f\) 呢？使用 map 即可。本题中，unordered_map、gp_hash_table、cc_hash_table 均超时。因为所有哈希表是可以被卡的，然而 map 的复杂度固定。衷心建议，在复杂度允许的情况下尽量使用 map，哈希实在有些玄学。

AC Link

Code 
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10,mod=1e9+7;
int T,n,b[N];map<LL,int>dp;
void work()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    dp[b[1]]=1;int sum=1;LL offset=0;
    for(int i=2;i<=n;i++)
    {
        offset+=-b[i];
        long long tmp=dp[b[i]+offset];
        dp[b[i]+offset]=sum;
        (sum+= ((sum-tmp+mod)%mod))%=mod;
    }
    printf("%d\n",sum);
}
int main(){cin>>T;while(T--)work(),dp.clear();return 0;}

CF1499E Chaotic Merge

摘要：

  1. 暴力转移题中式子，发现答案只与 \(r_1,r_2\) 有关。
  2. 去掉状态中 \(l_1,l_2\)，加入其它状态：上一个选了什么，总共选过什么。

首先尝试暴力转移题里给出的式子，容易发现，每次新加入一个字符时，需要讨论的只有结尾的状态，因为无论最初从哪里开始，只要不相邻，都不需要管。

因为需要记录上一个选了什么，所以加入一维 \(0/1\) 表示末尾的字符来自 \(x/y\) ；因为只有 \(x,y\) 都选过才合法，所以加入一维 \(0/1/2/3\)，用二进制表示 \(x/y\) 是否选过。

综上，设 \(f[i][j][0/1][k]\) 表示： “ 当前 \(x\) 串选到了第 \(i\) 个，\(y\) 串选到了第 \(j\) 个，\(z\) 串的末尾字符来自 \(x(0)/y(1)\)，已经选过了什么 ” 的方案数。

此处采用了由当前的状态向以后的状态转移，考虑是否能将 \(x/y\) 的下一字符加入，若能则考虑影响。具体地，转移时枚举 \(k\)，若当前 \(i/j\) 不是字符串结尾，并且与上一位不同，即可加入，由当前状态确认转移给谁。转移如下：

    for(int i=0;i<=n;i++)
    for(int j=0;j<=m;j++)
    {
        if(i<n)
            (dp[i+1][j][0][1]+=1)%=mod;
        if(j<m)
            (dp[i][j+1][1][2]+=1)%=mod;
        for(int k=0;k<4;k++)
        {
            if(i<n&&s[i]!=s[i+1])
                (dp[i+1][j][0][k|1]+=dp[i][j][0][k])%=mod;
            if(i<n&&t[j]!=s[i+1])
                (dp[i+1][j][0][k|1]+=dp[i][j][1][k])%=mod;
            if(j<m&&s[i]!=t[j+1])
                (dp[i][j+1][1][k|2]+=dp[i][j][0][k])%=mod;
            if(j<m&&t[j]!=t[j+1])
                (dp[i][j+1][1][k|2]+=dp[i][j][1][k])%=mod;
        }
    }

这里提供一种比较简洁的加法取模写法：

a=(a+b)%mod 可以写成 (a+=b)%=mod，可以避免大量重复导致的眼花甚至错误。

AC Link

Code 
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int N=1010;
int n,m;
char s[N],t[N];
int dp[N][N][2][4];
// s 串计算到 i；t 串计算到 j；z 的上一位来自 s/t；已经选了 s/t（00，01，10，11）；
int main()
{
    scanf("%s%s",s+1,t+1);
    n=strlen(s+1),m=strlen(t+1);
    for(int i=0;i<=n;i++)
    for(int j=0;j<=m;j++)
    {
        if(i<n)
            (dp[i+1][j][0][1]+=1)%=mod;
        if(j<m)
            (dp[i][j+1][1][2]+=1)%=mod;
        for(int k=0;k<4;k++)
        {
            if(i<n&&s[i]!=s[i+1])
                (dp[i+1][j][0][k|1]+=dp[i][j][0][k])%=mod;
            if(i<n&&t[j]!=s[i+1])
                (dp[i+1][j][0][k|1]+=dp[i][j][1][k])%=mod;
            if(j<m&&s[i]!=t[j+1])
                (dp[i][j+1][1][k|2]+=dp[i][j][0][k])%=mod;
            if(j<m&&t[j]!=t[j+1])
                (dp[i][j+1][1][k|2]+=dp[i][j][1][k])%=mod;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        ans+=dp[i][j][0][3];ans%=mod;
        ans+=dp[i][j][1][3];ans%=mod;
    }
    printf("%d\n",ans);
    return 0;
}

CF1536E Omkar and forest

摘要：

  1. 性质：所有填 \(0\) 的位置确定之后，一定只有一种情况或无解，无解当且仅当零个 \(0\)。

  2. \(cnt\) 个‘\(\#\)’，每个有两种安排，所以 \(2^{cnt}\)，并特判全为\('\#'\)。

神奇的思路。

如果性质成立，那么只需计算一次快速幂，并特判全是 \(\#\) 的情况（只有这种情况无解），设 \(cnt\) 为 ‘\(\#\)’ 的个数，答案为 $ 2^{cnt} - [cnt=nm] $。

以下是性质的证明。

事实上这就是 bfs 的描述证明啥。

类比边权为 \(1\) 的多源 bfs。从 填完 \(0\) 开始， 每次将周围的一圈更新最短路，由于 bfs 的性质，最后一定得到唯一的合法解。

唯一性来源于最短路；合法来源于边权为 \(1\)，即每一个 \(dis\) 不为 \(0\) 的点必由相邻的 \(dis\) 更小的点转移来，且不存在相邻两点 \(dis\) 之差超过 \(1\)。

AC Link

Code 
#include<bits/stdc++.h>
using namespace std;
const int &mod=1e9+7;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T,n,m,mp;char c;
    int cnt=0,ans=0,flag=0;
    cin>>T;while(T--)
    {
        cin>>n>>m;mp=n*m;
        while(mp--)
            cin>>c,cnt+=(c=='#');
        if(cnt==n*m)flag=1;
        ans=1;
        while(cnt--)(ans<<=1)%=mod;
        ans-=flag;
        printf("%d\n",ans);
        cnt=ans=flag=0;
    }
    return 0;
}

CF1523D Love-Hate

摘要：

  1. 对于某个合法答案，选 \(T\) 个人枚举子集，最终没访问到的概率是 \(2^{-T}\)，所以可以随机化。

  2. 每次随机，计算所有人与此人的交集，求超集个数不少于 \(\lceil \frac{n}{2} \rceil\) 的最大集合。

  3. 枚举子集 \(3^p\)，改为高维前缀和优化至 \(n \times 2^n\)。

tips：超集是指包含当前集合的集合。

抽象题。当时在 tag 里看到 probabilities 的时候还疑惑怎么会有概率，结果是随机化。

一个合法答案定义为，被至少 \(\lceil \frac{n}{2} \rceil\) 个人的集合包含。那么若本次没有选中，下次仍然没有选中的概率就是本次的一半，而 \(2^{-50} \approx 8.88 \times 10^{-16}\)…………所以随机化可过。不如说只要没写挂就很难错。

每次选中一个人，然后检查 \(n\) 个人，每个人算出他与选中的人的集合交集。

更快速地计算超集要用到高维前缀和。

首先考虑二维前缀和，可以把两维拆开分别做；进一步地，如果要求子集个数，设 集合对应着长度为 \(p\) 的 01 串，则可以视作 求一个 \(p\) 维的，每一维长度为 \(1\) 的 高维前缀和。

对于求子集个数，显然可以转为前缀和形式。对于求超集个数，如果倒着处理，即求前缀和的方向从 \(0 \rightarrow 1\) 变成 \(0 \leftarrow 1\)，同样可以利用前缀和处理。这样复杂度是 \(p\times 2^p\)。

求超集代码：

        for(int j=0;j<vrr.size();j++)
        {
            for(int i=1;i<=lim;i++)
            {
                if( (i & (1<<j)) == 0 )
                    f[i] += f[i ^ (1<<j)];
            }
        }

细节挺多，建议慢点写，但一定要准。

AC Link

Code 
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10;
int n,m,p;char ss[N];
LL a[N];int f[1<<15];
bool vis[N];
vector<int>vrr;
#define __count __builtin_popcount
#define __countLL __builtin_popcountll
mt19937 rnd(time(0));
int get()
{
    LL y=rnd()%n+1;return y;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++)
    {
        cin>>ss+1;
        for(int j=1;j<=m;j++)
            if(ss[j]=='1')a[i]^=1LL<<(j-1);
    }
    LL ans=0;
    int it,T=min(50,n);
    int cnt=0;
    while(T--&&cnt<n)
    {
        it=get();++cnt;
        if(a[it]==0)continue;
        
        vrr.clear();
        for(int j=1;j<=m;j++)
        {
            if(a[it]& (1LL<<(j-1)) )
                vrr.push_back(j);
        }
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;i++)
        {
            int s=0;
            for(int j=0;j<vrr.size();j++)
            {
                if( a[i] & (1LL<<(vrr[j]-1)) )
                    s^=1<<j;
            }
            f[s]++;
        }
        int lim=1<<vrr.size();lim--;

        for(int j=0;j<vrr.size();j++)
        {
            for(int i=1;i<=lim;i++)
            {
                if( (i & (1<<j))==0  )
                    f[i] += f[i ^ (1<<j)];
            }
        }   
        int now=0;
        for(int i=1;i<=lim;i++)
        {
            if(f[i]*2>=n  && __count(i) > __count(now) )
                now = i;
        }
        if( __count(now) > __countLL(ans) )
        {
            ans=0;
            for(int i=0;i<vrr.size();i++)
            {
                if(now&(1<<i))ans|=(1LL<<(vrr[i]-1));
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(ans&(1LL<<(i-1)))cout<<"1";
        else cout<<"0";
    }cout<<endl;
    return 0;
}

CF1419E Fib-tree

摘要：

  1. 转化：如果一个树合法，那么一定能经合法过程全拆成单点。

  2. 性质：每次拆大小 \(Fib_i\) 的，一定拆成 \(Fib_{i-1},Fib_{i-2}\)。

  3. 每次拆只有两种拆法且等价。所以暴力即可，复杂度 \(nlog_\phi n\)。

抽象结论题。说它抽象是因为证明很多比较抽象，感觉不严谨又说不明白看不懂。

我们考虑一个树合法，则会一直在合法状态下断成 \(n\) 个点，所以如果能有一种方式，使得可以在最优策略下模拟，即如果做出来了自然有解，而做不出来也一定无解，那么这题就做完了，因为 Fib 增长很快，是 \(\phi^n\) 的，所以每次割之前重新跑一遍 dfs 维护真子树，复杂度是 \(nlog_\phi n\)。此处 \(\phi\) 是黄金分割比，详情请百度 Fibonacci Sequence 相关知识。

性质一，\(F_{n}\) 一定只能拆成 \(F_{n-1}\) 和 \(F_{n-2}\)

考虑斐波那契数列（以下简称 Fib）的性质。如果要拆 \(F_{n}\) 一定只能拆成 \(F_{n-1}\) 和 \(F_{n-2}\)，比较显然，可以通过解方程的方式证明（官方题解），也可以简单考虑：如果不在这两个里选，那无论选什么，减完的数都会大于这两个，没得选了。

性质二：如果存在两条边，先切哪条都是等价的

接着考虑怎么拆，每次随便找一个 \(Fib_{n-1}\) 或者 \(Fib_{n-2}\) 拆行不行？行，然而找到的大部分不是非常严谨（主要是我看不懂）的证明，包括官方题解，但还有一个算挺靠谱的：

Link to the proof

这个是用归纳法证的。首先对于 \(Fib_3\) 是满足的，这是真显然。

假设直到 \(Fib_{n-1}\) 都满足性质二，且对于\(Fib_n\) 有 \(a,b\) 两条可以切出 \(Fib_{n-2}\) 的边。

如果先切 \(a\)，之后 \(b\) 在 \(Fib_{n-1}\) 里面，由于性质二，可以立马切 \(b\)；如果先切 \(b\) 那么可以立马切 \(a\)。

综上，在前提条件下无论先切哪条都可以紧接着把另一条切了，于是两种切法等价了。

如果只有一个合法方案，直接切就可以了。

有的同学可能会想，随便找一个点当根，不会存在由于选的根在应切掉的子树内而找不到的情况吗？事实上我们相当于枚举了每一条边，所以不会有漏掉的情况。

AC Link

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

const int N=2e5+10;
int Fib[]={0,1,1,2,3,5,8,13,21,34,55,89,
144,233,377,610,987,1597,2584,4181,6765,
10946,17711,28657,46368,75025,121393,196418};
bool mp[N];
void init_Fibonacci()
{
    for(int i=1;i<=27;i++)
        mp[Fib[i]]=1;
}
int n;
struct edge{int to,nxt;};
edge e[2*N];int head[N],tot;
void add(int u,int v)
{
    e[++tot]={v,head[u]};head[u]=tot;
}
int fa[N],sz[N],dfn[N],rk[N],dc;bool cut[N];
void dfs0(int u,int pa)
{
    fa[u]=pa;sz[u]=1;rk[dfn[u]=++dc]=u;
    for(int i=head[u];i;i=e[i].nxt)
        if ( (e[i].to^pa) and (!cut[e[i].to]) )
            dfs0(e[i].to,u),sz[u]+=sz[e[i].to];
}
bool dfs1(int u)
{
    if(sz[u]==1)
    {
        return true;
    }
    if(mp[sz[u]]==0)
    {
        return false;
    }
    for(int i=dfn[u]+1;;)
    {
        int v=rk[i];
        if(cut[v])
        {
            i+=sz[v];
        }
        else if(mp[sz[v]] and mp[sz[u]-sz[v]])
        {
            cut[v]=1;dc=0;dfs0(u,fa[u]);dfs0(v,fa[v]);
            bool res1=dfs1(u),
                 res2=dfs1(v);
            return res1 && res2;
        }
        else 
        {
            i++;
        }
        if(i>=dfn[u]+sz[u])break;
    }
    // printf(" at %d %d,false\n",u,sz[u]);
    return false;
}
void debug()
{
    return ;
    for(int i=1;i<=n;i++)printf("%d ",fa[i]);puts("");
    for(int i=1;i<=n;i++)printf("%d ",sz[i]);puts("");
    for(int i=1;i<=n;i++)printf("%d ",dfn[i]);puts("");
    for(int i=1;i<=n;i++)printf("%d ",rk[i]);puts("");
}
int main()
{
    init_Fibonacci();
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs0(1,0);
    bool ans = dfs1(1);
    puts(ans?"YES":"NO");
    debug();
    return 0;
}

CF1527D Mex Tree

摘要：

  1. T转化 ：\(mex\) 为 \(x\) 的等于 包含到 \(x-1\) 的减去包含到 \(x\) 的。

  2. 以 \(0\) 为根模拟路径，并用 \(size\) 计算方案数。

  3. 注意细节。

套路好题。

首先考虑，如果使 \(mex\) 为 \(0\)，只需不经过 \(0\) 即可，简单 DP 维护子树内路径可解。

接下来考虑继续推，如果 \(mex_{path}=x\) 那么需要包含 \([1,x-1]\) 所有点，并不包含 \(x\)，其余点任意。因此，我们考虑维护 \(f_i\) 表示包含 \([1,i]\) 所有点的路径数。

接下来是比较重要的地方，设 \(mex_x\) 为 \(mex=x\) 的方案数，那么有转化：

\[mex_x = f_{x-1} - f_{x} \]

于是做完了。

一些实现：

\(f_{i-1} \rightarrow f_{i}\) 时，路径一定会变得更长或无解，因此我们只需每次判断 \(i\) 与 之前的路径端点的祖先关系，并用两端点外侧的 \(size\) 相乘计算答案。

具体地，如果已经在路径中就继承，如果是端点的后代就将端点拽下来，如果 \(LCA\) 在路径中间就说明从这里开始都无解。注意特判一端在 \(0\) 的情况。细节略多但不多。

AC Link

Code 
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e5+10;
struct edge {int to,nxt;};
edge e[N*2];int head[N],tot;
void add(int u,int v)
{
    e[++tot]={v,head[u]};head[u]=tot;
}
int n,fa[N],dep[N],sz[N];
int dfn[N],dc,st[N][25];
LL sum[N],f[N];int L,R;
void dfs0(int u,int pa)
{
    dfn[u]=++dc;st[dc][0]=pa;
    fa[u]=pa;dep[u]=dep[pa]+1;sz[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;if(v==pa)continue;
        dfs0(v,u);
        sum[u]+=1ll*(sz[u]-1)*sz[v];
        sz[u]+=sz[v];
    }
}
int get(int u,int v)
{
    return (dfn[u]<dfn[v])?u:v;
}
void init()
{
    for(int i=1;i<=__lg(n);i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            st[j][i]=get(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
int LCA(int u,int v)
{
    if(u==v)return u;
    if( (u=dfn[u]) > (v=dfn[v]) )swap(u,v);
    int d=__lg(v-u);
    return get(st[u+1][d],st[v-(1<<d)+1][d]);
}

bool flag=1;
void work()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs0(0,0);
    init();
    L=R=0;
    LL all=0;
    for(int i=0;i<n;i++)
        all += sum[i]+sz[i]-1;
    f[0]=sum[0]+sz[0]-1;
    int it=0;
    for(int i=1;i<n;i++)
    {
        int cal=LCA(i,L),car=LCA(i,R);
        if(cal==L&&car==R)
        {
            int tmp=0;
            if(!it)
                for(int j=head[L];j;j=e[j].nxt)
                {
                    int v=e[j].to;
                    if (dep[v]>dep[L]&&LCA(v,i)==v)
                    {
                        it=v;break;
                    }
                }
            tmp= (sz[0]-sz[L]+sz[L]-sz[it]);
            f[i] = 1ll * tmp * sz[i];
            R=i;
        }
        else 
        {
            if(cal==L&&car==0)
            {
                f[i] = 1ll * sz[R] * sz[i];
                L=i;
            }
            else if(car==R&&cal==0)
            {
                f[i] = 1ll * sz[L] * sz[i];
                R=i;
            }
            else if(cal==i||car==i)
            {
                f[i]=f[i-1];
            }
            else 
            {
                break;
            }
        }
    }
    printf("%lld ",all-f[0]);
    for(int i=1;i<=n;i++)
    {
        printf("%lld ",f[i-1]-f[i]);
    }puts("");
}
void clear()
{
    for(int i=0;i<n;i++)
        dep[i]=sz[i]=fa[i]=head[i]
        =sum[i]=f[i]=0;
    L=R=0;dc=0;tot=0;
}

signed main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        work(),clear(); 
    }
    return 0;
}

CF1499F Diameter Cuts

摘要：

  1. 暴力 DP，将子树内最大深度放入状态，看上去 \(O(n^2 m)\)。

  2. 任选优化，或者暴力。

  3. 转移时用临时数组存储避免算重。

DP 优化好题，有各式各样的优化方法，其实暴力就可过。

朴素 DP：

先考虑 DP 状态，由于关系到直径，所以考虑维护子树内最大深度。

至于子树直径或者说次长不需要考虑，因为可以由转移新的子节点时确定合法性。

具体地，设 \(f_{u,i}\) 表示 \(u\) 子树内最深（距离 \(u\)）为 \(i\) 的方案数。

我们考虑动态地向子树中加入子节点，并计算它割断与否的影响。

如果断开，互不影响，则有 ：

\[f_{u,i}' = f_{u,j} \times \sum_{k=0}^{m} f_{v,k} \]

不断开，那么原先最长链加新的最长链不能超过 \(m\)。

\[f_{u,j}' = f_{u,j} \times \sum_{j+k+1<m}f_{v,k} \]

注意，由于 \(f_{u,j}'\) 与 \(f_{u,j}\) 要分开，所以每次合并子节点时要开个 \(tmp\) 记录一下。

那么我们考虑优化……吗？我直接：

        dfs(v,u);
		for(int j=0;j<=min(mxd[u]-dep[u]);j++)
		for(int k=0;k<=min(mxd[v]-dep[u]);k++)

复杂度分析：

好，在优化之前，我们想想复杂度。它真是 \(O(n^2 m)\) 吗？如是。它真 TLE 吗？如 T。

实际上复杂度是 \(O(n^2)\) 的：

如果这个点只有一个子节点就是 \(O(1)\)，这部分加起来 \(O(n)\)；如果有多个，那么相当于每次合并两个子树（可以看成两条链），代价为最大深度相乘。最坏情况显然是从大到小合并，是 \(\sum len \times \max - \max \le n \times \max\)，所以复杂度不超过 \(O(n^2)\)，所以做完了。

碎碎念：

这个问题可以看成是一些物品，每次合并两个，代价是两值相乘，结果是两值取最大。

接下来的部分已经与本题无关。

容易用调整法证明，代价最大是从大到小合并，代价最小是从小到大合并。

具体地，先排序，然后钦定合并为由小的指向大的，对于 \(a<b<c<d\)，讨论交换产生的影响。更具体地，\(ab,cd\) 相对于其余任意形式，代价方面和最大值方面都是更优的。 证明代价最大也可以直接取 \(max\)。

对于这道题，不止有这一种方式，也可以推推式子用前缀和、前后缀积等方法优化。

另外，由于本题 \(n,m\) 同级， \(O(n^2)\) 的转移是被允许的，然而如果 \(n\) 更大， \(m\) 更小，也许就需要一些别的方法变为 \(O(nm)\) 的做法。

长链剖分优化 DP：

首先说一下长链剖分。

和重链剖分差不多，以后代深度最深的点为重儿子，按长度剖分。相比重剖，长剖跳链是 $\sqrt n $ 的。可以支持 \(O(n\log n)-O(1)\) 求树上 \(k\) 级祖先，也可以优化与深度有关（包含深度维）的树上 DP。

假设 \(u\) 只有一个儿子 \(v\)，\(f[i][j]\) 为一个数组，其中 \(i,j\) 分别表示点和深度，比如：“\(i\) 子树内与 \(i\) 距离为 \(j\) 的点的数量”。

我们发现，\(f[u]\) 与 \(f[v]\) 长得差不多，把 \(f[v]\) 整体挪一位即可得到 \(f[u]\)。

具体地，\(f[u][0]=1,f[u][i]=f[v][i-1]\)。

那要不你俩用一个数组得了。

众所周知，指针有时候是个好东西。我们可以直接把 \(f[v]\) 指在 \(f[u]+1\) 的位置，这样到时候访问就不用重新算了。当然，也可以手动模拟指针，甚至有 vector 的 swap 写法。

于是，对于重儿子的信息，我们 \(O(1)\) 继承；对于轻儿子，也就是单独的一条长链，我们暴力转移。假设每转移一对点是 \(O(s)\) 的，那转移一条长链是 \(O(len\times s)\) 的，相当于每个点只在链顶并入链顶父亲时被转移一次，即 \(\sum len \times s = n \times s\)。

于是我们得到了时间 \(O(nm)\)、空间\(O(n)\) 的做法。注意，这种做法不支持在计算结束后任意访问某一节点的 \(f\) 数组，因为重儿子的数组会被父亲更新。

指针部分的代码：


int *f[N],*now,dp[N],tmp[N];

main()

    dfs1(1,0);
    now = dp;f[1]=now;now+=lev[1];//lev表示链长度（点数）
    dfs2(1,0);

dfs2(int u,int v)
    if(son[u])
    {
        f[son[u]] = f[u] + 1;
        dfs2(son[u],u);
    }

    f[v] = now;now += lev[v];

        for(int j=0;j<=min(lev[u]-1,m);j++)
            for(int k=0;k<=min(lev[v]-1,m);k++)

细节：

一定注意子树内到根最长距离是链长（点数）减一，而不是链长。

如果是其他写法不会错，因为那里是空的。但如果使用了指针实现的长剖，就会把别的东西拿进来，症状为答案更大。

有一篇题解开了二倍空间，是因为两条长链之间空了一个，以弥补枚举时越界的问题。

AC Link

Code 
// LUOGU_RID: 132975308
#include<bits/stdc++.h>
using namespace std;

const int N=5010,M=5010;
const int mod=998244353;
int n,m;
int dep[N],mxd[N],lev[N],son[N];
int *f[N],*now,dp[N],tmp[N];
struct edge{int to,nxt;};
edge e[2*N];int head[N],tot;
void add(int u,int v)
{
    e[++tot]={v,head[u]};head[u]=tot;
}
void dfs1(int u,int pa)
{
    dep[u]=dep[pa]+1;
    // lev[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;if(v==pa)continue;
        dfs1(v,u);
        if(lev[v]>lev[son[u]])son[u]=v;
    }
    lev[u]=lev[son[u]]+1;
}
void dfs2(int u,int pa)
{
    f[u][0]=1;
    //注意枚举时到 （节点数-1） lev-1
    if(son[u])
    {
        f[son[u]] = f[u] + 1;
        dfs2(son[u],u);
        tmp[0]=0;
        for(int i=0;i<=min(lev[son[u]]-1,m);i++)
        {
            (tmp[0]+=f[son[u]][i])%=mod;//f[u][0] <- sum
        }
        f[u][0]=tmp[0];
    }
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;if(v==pa||v==son[u])continue;
        f[v] = now;now += lev[v];
        dfs2(v,u);
        for(int j=0;j<=min(lev[u]-1,m);j++)
            tmp[j]=0;
        for(int j=0;j<=min(lev[u]-1,m);j++)
        {
            for(int k=0;k<=min(lev[v]-1,m);k++)
            {
                (tmp[j]+=1ll*f[u][j]*f[v][k]%mod)%=mod;
                if(j+k+1<=m)
                    (tmp[max(j,k+1)]+=1ll*f[u][j]*f[v][k]%mod)%=mod;
            }
        }
        for(int j=0;j<=min(lev[u]-1,m);j++)
            (f[u][j]=tmp[j])%=mod;
        //f[u][j] = tmp[j]，而非 += 因为状态逻辑上应包含已合并的全部子结点
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs1(1,0);
    now = dp;f[1]=now;now+=lev[1];//加上节点数
    dfs2(1,0);
    int ans=0;
    for(int i=0;i<=min(lev[1]-1,m);i++)
        (ans+=f[1][i])%=mod;
    printf("%d\n",ans);
    return 0;
}

标签：2200,sz,head,const,int,void,CF,集合,杂题
From： https://www.cnblogs.com/hx-rand/p/17806242.html

相关文章

  • CF1842G
    第一次听没听懂，补个笔记。弄懂这种奇妙拆贡献后感觉非常厉害。答案的形式为：\(\prod(a_i+k\cdotv)\)，这些\(v\)是前面的操作带来的影响。我们考虑一个个加入这个\((a_i+k\cdotv)\)，并且维护很多个等价类，使得这个值可以根据分开等价类的那个标志被确认。\(k\)，不过是前......
  • CF1866D Digital Wallet 题解
    Problem-1866D-CodeforcesDigitalWallet-洛谷不妨为选数钦定一个顺序：不同行之间无影响，列从左到右取一定不劣。设计状态：设\(dp_{i,j}\)表示前\(i\)次操作操作到第\(j\)列的最大答案转移：因为对于同一列不互相影响，因此枚举这一列取\(c\)个数，显然取这一列数......
  • 「杂题乱写」Ynoi
    「杂题乱写」Ynoi点击查看目录目录「杂题乱写」YnoiP7710[Ynoi2077]stdmxeypzP5356[Ynoi2017]由乃打扑克P5309[Ynoi2011]初始化P5046[Ynoi2019模拟赛]YunolovessqrttechnologyI由于Ynoi道道卡常且常数受一些常量影响较大，为方便表示复杂度，本文记阈值为\(B\)......
  • CF DP 题乱做（续更）
    CF566F$1500$容易考虑到$n^2$做法：设$dp_i$为第$i$个数选的答案，对于排好序的序列，枚举前面的数$a_j$，如果$a_j|a_i$就转移，时间复杂度易知$O(n^2+n\logn)$。由于$a$至于很小，延续刚才的思路，设$dp_i$为选值为$i$的答案。那么她可以更新她的所有倍数，枚举倍数即可。......
  • CF1866M Mighty Rock Tower 题解
    Problem-1866M-CodeforcesMightyRockTower-洛谷先考虑一个\(O(n^2)\)的dp设计状态：\(dp_i\)表示搭\(i\)层的期望转移：\(dp_i=dp_{i-1}\times(1-P_i)+\sum\limits_{j=i}^{n-1}dp_j\timesP_{j+1}^{j-i+1}\times(1-P_{j+1})\)，显然是有后效性的，但我们展开......
  • vcftools 快速安装日志
     下载https://vcftools.github.io/examples.htmltar-xvfvcfools.0.X.XX.tar.gzexportPERL5LIB=/path/to/your/vcftools-directory/src/perl/cdvcftools/先执行./autogen.sh报错autoreconf找不到，执行yuminstall autoreconf./configure 如果这一步执行报错，缺少c++......
  • 杂题练习
    stl众所周知一般来说，随着社会经济的不断发展，stl越来越成为一款强大的工具。著名cp选手i_wish_a_gilrfriend曾说过：stl，启动！无敌山鸡王说：我在学习了算法近一年后才了解stl，这是我的巨大损失。五星上将麦克阿瑟曾说过，如果上帝不让我使用stl，那我将用枪指向上帝。下面是练习使用stl......
  • linux服务器安装python curl_cffi
    """在windows或mac上，直接pip3installcurl_cffi就能使用，但是在linux中，可能会缺少证书以下是Linux中的安装步骤:"""#安装第三方库pip3installcurl_cffi​#下载证书wgethttps://curl.se/ca/cacert.pem​#将证书添加到site-packagesmvcacert.pem/usr/local/lib/python3.8/si......
  • 棱镜七彩兼容CCF版开源漏洞信息描述规范COSV Schema 1.0
    CCF版开源漏洞信息描述规范COSVSchema1.0（以下简称“COSVSchema1.0”）已于前期正式发布，棱镜七彩作为COSVSchema1.0制定工作的重要成员积极响应规范内容，目前公司产品与漏洞推送服务已经实现COSVSchema1.0兼容。开源软件在现代软件开发中占据着重要作用，因此开源软件中存在的开源......
  • CF练习题18
    这次的题都是什么怪物！！！ShortColorfulStrip因为\(n=m\)，所以最终的形态一定是\(n\)的一个排列。根据题意，发掘几个性质：一个区间染色，一定最先对其中颜色最小的染色。染色要求覆盖的点颜色完全相同。对于第一次来说，先找到颜色为\(1\)的点，位置是\(p\)。染色的区间是\([......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99