打星就是不会，后来学的。

[ARC103 F]

solution

题面：给出一个长度为 的序列 ，要求构造一个 个点的树，使得对于点 而言，其他点到它的距离之和等于 ，树的边权为 。注意， 互不相同。

做法：开始没看到 互不相同这个条件想了半天，然后才发现自己是个大傻子，不过有相同是不是也可以反悔贪心啊。

首先注意到直接维护距离之和是不容易的，考虑换根 dp，可以注意到从某个父亲 换到 的时候有递推式，

发现这东西并不好直接搞，因为看起来我们无法确定 的顺序，不容易去构造。但注意到右边是 ，这东西容易联想到重心，于是我们设根为重心，那么除根以外的 都是小于等于 的，那么就知道儿子的 都是大于父亲的，于是 从大到小排序，从叶子开始往里填数。而式子可以被化成 ，于是扔一个 进来就看看有没有右边等于它的，然后因为 互不相同，所以这个 一定要一次性把所有右边等于它的合并在一起，这样做就是唯一的，所以是否有解也就判好了。可以二分或者 map 维护下右边的值，时间复杂度 。

最后记得检验下 合不合法，由于是换根递推的，所以只用随便检验一个就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//2022.5.5 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    pair<LL,int> D[N];
    int n;
    map<LL,vector<int> > M;
    int sz[N],tot;
    int fa[N];
    LL ans;
    inline void MAIN(const res &Case){
        n=read();
        for(res i=1;i<=n;i++)D[i]=mp(Read(),i);
        sort(D+1,D+n+1,[&](const auto &A,const auto &B){return A.fi>B.fi;});
        for(res i=1;i<=n;i++){
            auto [d,p]=D[i];
            if(M.count(d)){
                for(auto x:M[d])sz[p]+=sz[x],fa[x]=p;
                tot-=(int)M[d].size()-1,sz[p]++,M.erase(d),M[d-n+2ll*sz[p]].pb(p),ans+=sz[p]-1;
            }
            else {
                sz[p]++,M[d-n+2ll*sz[p]].pb(p),tot++,ans+=sz[p]-1;
            }
        }
        if(tot!=1||ans!=D[n].fi)puts("-1");
        else {
            for(res i=1;i<=n;i++){
                if(fa[i])printf("%d %d\n",i,fa[i]);
            }
        }
    }
}

[*ARC140 D]

solution

题面：给出一个数组 ，其中一些位置的数未知。 和 连一条无向边，未知的 随意填一个 之间的数，问所有方案的连通块数的和。

做法：我是不是个大傻子？拆贡献算最终答案都不会了？

搞出现在的所有连通块后，注意到一个很好的性质，即每个连通块出边最多只有一条。直接拆贡献算最终答案，考虑每个连通块对最终答案的贡献，那么就是算若干个连通块合并起来的方案数，容易发现这东西没想象中的好算，因为合并方式太多了。注意到另一个性质，每个连通块有且只有一个环。那么我们直接枚举成环情况，这样就不用考虑连通块是如何合并的了。因为对于一个环而言，其他点的随意连边并不改变这个环对答案的贡献。而成环的方案数是容易的，考虑将这若干个连通块排列好，按序向下一个连通块连边即可。于是就可以 或者 做完此题了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//2022.5.16 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e3+10;
namespace MAIN{
    int n;
    int a[N];
    int fa[N],sz[N];
    inline int find(res x){
        while(x!=fa[x])x=fa[x]=fa[fa[x]];
        return x;
    }
    int B[N],bx,A;
    int f[N][N],vis[N];
    inline void MAIN(const res &Case){
        n=read();
        for(res i=1;i<=n;i++)a[i]=read(),fa[i]=i,sz[i]=1;
        res now=n;
        for(res i=1;i<=n;i++){
            if(a[i]!=-1){
                res x=find(i),y=find(a[i]);
                if(x!=y)fa[x]=y,sz[y]+=sz[x],now--;
            }
        }
        for(res i=1;i<=n;i++){
            if(a[i]==-1){
                res x=find(i);
                B[++bx]=sz[x],vis[x]=1;
            }
        }
        for(res i=1;i<=n;i++){
            if(a[i]!=-1){
                res x=find(i);
                if(vis[x])continue;
                vis[x]=1;
                A++;
            }
        }
        f[0][0]=1;
        for(res i=1;i<=bx;i++){
            f[i][0]=1;
            for(res j=1;j<=bx;j++){
                f[i][j]=Add(f[i-1][j],mul(f[i-1][j-1],B[i]));
            }
        }
        res ans=mul(A,qpow(n,bx)),fac=1;
        for(res i=1;i<=bx;i++)add(ans,mul(fac,mul(qpow(n,bx-i),f[bx][i]))),fac=mul(fac,i);
        printf("%d\n",ans);
    }
}