题面翻译

给你一个NN个节点的树，求一个1⋯N1\cdots N的排列(p1,p2,⋯pN)(p_1,p_2,\cdots p_N) ，使得∑dist(i,pi)\sum dist(i,p_i)最大。

求这样的排列的个数。答案对109+710^9+7取模。

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
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;
typedef long long ll;
typedef pair<int,int>ttfa;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=100005;
const ll MOD=1000000007;
int n,root,siz[N],fiz[N];
ll fac[N],ifc[N],dp[N],ans;
inline ll C(ll n,ll r){return fac[n]*ifc[r]%MOD*ifc[n-r]%MOD;}
vector<int>edge[N];
inline ll fpr(ll b,ll t=MOD-2,ll x=1){
	for(;t;t>>=1,b=b*b%MOD)
		if(t&1)x=x*b%MOD;
	return x;
}
void dfs(int u,int f){
	siz[u]=1,fiz[u]=0;
	for(auto v:edge[u]){
		if(v==f)continue;
		dfs(v,u);
		siz[u]+=siz[v];
		fiz[u]=max(fiz[u],siz[v]);
	}fiz[u]=max(fiz[u],n-siz[u]);
	if(fiz[u]<fiz[root])root=u;
}
int main(){
	n=read();
	fac[0]=ifc[0]=1;
	for(int i=1;i<=n;++i)fac[i]=fac[i-1]*i%MOD;
	ifc[n]=fpr(fac[n]);
	for(int i=n-1;i>=1;--i)ifc[i]=ifc[i+1]*(i+1)%MOD;
	for(int i=1;i<n;++i){
		int u=read(),v=read();
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	fiz[root=0]=n;dfs(1,0);dfs(root,0);
	dp[0]=1ll;
	for(auto v:edge[root]){
		int s=siz[v];
		for(int i=n;i>=0;--i){//背包
			for(int j=1;j<=min(i,s);++j){
				ll tmp=C(s,j)*C(s,j)%MOD*fac[j]%MOD;
				dp[i]=(dp[i]+dp[i-j]*tmp%MOD)%MOD;
			}
		}
	}
	for(int i=0;i<=n;++i)
		ans=(ans+((i&1)?-1ll:1ll)*dp[i]*fac[n-i]%MOD+MOD)%MOD;
	printf("%lld\n",ans);
	return 0;
}

只求最大值的网络赛代码

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
#define ll long long
# define int long long
#define ull unsigned long long
#define pii pair<int,int>
 
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"
#define alls(x) (x).begin(), (x).end()
#define fs first
#define sec second
const int N = 1e6 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
const double PI = acos(-1.0);
int n, m;
int a[N];
int ans=0;
struct edge{
    int v,w;
};
vector<edge>e[N];
int sz[N];
void dfs1(int u,int fa){
    sz[u]=1;
    for(auto [v,w]:e[u]){
     
        if(v==fa)continue;
        dfs1(v,u);
        sz[u]+=sz[v];
    }
}
void dfs2(int u,int fa){
    for(auto [v,w]:e[u]){
        if(v==fa)continue;
        ans+=2*w*min(sz[v],n-sz[v]);
        dfs2(v,u);
    }
}
void solve(){
    cin>>n;
    for(int i=1;i<=n-1;i++){
        int u,v,w;cin>>u>>v>>w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    dfs1(1,0);
    dfs2(1,0);
    cout<<ans<<endl;
     
}
signed main() {
    cin.tie(0);
     
    ios::sync_with_stdio(false);
 
   int t=1;
   //cin>>t;
    while (t--) {
solve();
    }
    return 0;
}

题目大意

有一个n个节点的树（编号1~n）。树上的每一个边都是正值。

我们定义两点之间的距离d(v,u)d(v,u)为这两点最短路径边的权值之和。

设数列pp为一个1~n的全排列。求使得∑i=1nd(i,pi)\sum_{i=1}^n d(i,p_i)最大的、字典序列最小的全排列pp。

输入格式

第一行是一个正整数 $n (1 \le n \le 10^5) $

接下来n-1行是三个整数$ u_{i},v_{i},w_{i} (1<=u_{i},v_{i}<=n; 1<=w_{i}<=10^{5}) ，分别代表，分别代表 u_{i}到到v_{i}有一条权值为有一条权值为w_i$的路径

数据保证这是一棵树

输出格式

第一行是所求的最大和

第二行是所求的字典序列最小的全排列

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
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
	x=0;char c=getchar(),f=0;
	for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
	for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
const int N=100005;set<int>nd[N],id;set<pair<int,int> >dd;int nid=0;
struct edge{int to,w,nxt;}e[N<<1];int et,head[N],d[N],p[N];
int n,sz[N],rt,dfn[N],nfd[N],dt,f[N],tag[N];ll rs=0;
inline void adde(int x,int y,int w) {e[++et]=(edge){y,w,head[x]},head[x]=et;}
inline void getrt(int x,int fa)
{
	sz[x]=1;int mx=0;for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa)
		getrt(e[i].to,x),sz[x]+=sz[e[i].to],mx=max(mx,sz[e[i].to]);
	mx=max(mx,n-sz[x]);if(mx<=n/2) rt=x;
}
inline void dfs0(int x,int fa)
{
	dfn[x]=++dt,nfd[dt]=x,sz[x]=1,f[x]=fa;
	for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa)
		dfs0(e[i].to,x),sz[x]+=sz[e[i].to],rs+=2ll*min(sz[e[i].to],n-sz[e[i].to])*e[i].w;
}
int main()
{
	read(n);for(int i=1,x,y,w;i<n;i++) read(x,y,w),adde(x,y,w),adde(y,x,w);
	if(n==1) return puts("0\n1\n"),0;else if(n==2) return printf("%lld\n2 1\n",2ll*e[head[1]].w),0;
	getrt(1,0),dfs0(rt,0),printf("%lld\n",rs);
	for(int i=head[rt],x;i;i=e[i].nxt)
	{
		++nid,x=e[i].to;for(int l=dfn[x];l<dfn[x]+sz[x];l++) nd[tag[nfd[l]]=nid].insert(nfd[l]);
		id.insert(*nd[nid].begin()),dd.insert(make_pair(d[nid]=n-2*nd[nid].size(),nid));
	}
	nd[tag[rt]=++nid].insert(rt),dd.insert(make_pair(d[nid]=n-2,nid)),id.insert(rt);
	int tg=0;for(int i=1;i<=n;i++)
	{
		int ps=tag[i],tw;dd.erase(make_pair(d[ps],ps));
		if(dd.begin()->first+tg==0&&dd.begin()->second!=tag[rt]) tw=dd.begin()->second;
		else if(tag[*id.begin()]==ps&&i!=rt) tw=tag[*++id.begin()];else tw=tag[*id.begin()];
		int qw=*nd[tw].begin();p[i]=qw,tg--,dd.erase(make_pair(d[tw],tw));
		id.erase(qw),nd[tw].erase(nd[tw].begin());if(!nd[tw].empty()) id.insert(*nd[tw].begin());
		dd.insert(make_pair(++d[ps],ps)),dd.insert(make_pair(++d[tw],tw));
	}
	for(int i=1;i<=n;i++) printf("%d%c",p[i],i==n?'\n':' ');
	return 0;
}

[ABC160F] Distributing Integers

题面翻译

有一颗节点编号为11至NN的树,第ii条边连接点aia_i和bib_i。对于11至NN的每个kk进行如下操作::

  • 按如下操作在树上每个点写一个数字::
    • 在点kk上写上11
    • 按从22到NN的顺序将数写在节点上::
      • 选择一个仍未写有数字且与已写有数字的点相邻的点,如果有多个这样的点,随机选择一个。
  • 输出所有写法的数量(结果模109+710^9+7)

就是从叶子开始求拓扑序的数量

image-20240512040300303

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN=200010,P=1e9+7;
int n,x,y,eg,hd[MAXN],ver[2*MAXN],nx[2*MAXN],siz[MAXN],f[MAXN];
void add_edge (int x,int y) {
	ver[++eg]=y;
	nx[eg]=hd[x];
	hd[x]=eg;
	return;
}
int qpow (int a,int b) {
	int res=1;
	while (b) {
		if (b&1) {res=(1ll*res*a)%P;}
		a=(1ll*a*a)%P,b>>=1; 
	}
	return res;
}
void dfs1 (int x,int fa) {
	siz[x]=1;
	for (int i=hd[x];i;i=nx[i]) {
		if (ver[i]==fa) {continue;}
		dfs1(ver[i],x);
		siz[x]+=siz[ver[i]];
	}
	f[1]=(1ll*f[1]*siz[x])%P;
	return;
}
void dfs2 (int x,int fa) {
	for (int i=hd[x];i;i=nx[i]) {
		if (ver[i]==fa) {continue;}
		f[ver[i]]=(1ll*f[x]*((1ll*(n-siz[ver[i]])*qpow(siz[ver[i]],P-2))%P))%P; 
		dfs2(ver[i],x);
	}
	return;
}
int main () {
	scanf("%d",&n);
	f[1]=1;
	for (int i=1;i<=n-1;i++) {
		scanf("%d%d",&x,&y);
		add_edge(x,y),add_edge(y,x);
	}
	dfs1(1,0);
	dfs2(1,0);
	int tmp=1;
	for (int i=1;i<=n;i++) {tmp=(1ll*tmp*i)%P;}
	for (int i=1;i<=n;i++) {printf("%d\n",(1ll*tmp*qpow(f[i],P-2))%P);}
	return 0;
}

**题意:求多个有根树构成的森林的拓扑序方案数 对10^9 + 7取模

*思路:每棵子树的序号转换成从 1 开始不重复的递增序号,加上一个超级源点 0 将其转化为求单棵有根树的拓扑序方案数

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;
#define __T int csT;scanf("%d",&csT);while(csT--)
#define endl '\n'
const int mod=1e9+7;
const double PI= acos(-1);
const double eps=1e-6;
const int N=2e5+7;

int n,c,q,u,cnt;
struct node{
    int nx,to;
}e[100033];//记得多开几条边用于超级源点与每棵树根结点的连边
int h[100003];
long long dp[100003],jc[100003];
long long qpow(long long a,long long x)
{
    long long d=a,sum=1;
    while(x>0)
    {
        if(x%2==1)
        {
            sum=(sum*d)%mod;
        }
        x>>=1;
        d=(d*d)%mod;
    }
    return sum;
}
long long inv(long long x)
{
    return qpow(x,mod-2);
}
int sz[100003];
void szdfs(int at)
{
    sz[at]=1;
    for(int i=h[at];~i;i=e[i].nx)
    {
        int to=e[i].to;
        szdfs(to);
        sz[at]+=sz[to];
    }
}
void dpdfs(int at)
{
    dp[at]=jc[sz[at]-1];
    for(int i=h[at];~i;i=e[i].nx)
    {
        int to=e[i].to;
        dpdfs(to);
        dp[at]=(dp[at]*dp[to]%mod*inv(jc[sz[to]]))%mod;
    }
}
inline void sol()
{
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    memset(sz,0,sizeof sz);
    q=cnt=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&c);
        e[++cnt].to=q+1;
        e[cnt].nx=h[0];
        h[0]=cnt;
        for(int j=2;j<=c;++j)
        {
            scanf("%d",&u);
            u=q+u;
            e[++cnt].to=q+j;
            e[cnt].nx=h[u];
            h[u]=cnt;
        }
        q+=c;
    }
    jc[0]=1;
    jc[1]=1;
    for(int i=2;i<=q;++i)jc[i]=(jc[i-1]*i)%mod;//预处理好模意义下的阶乘
    szdfs(0);//先求出每个结点的 size
    dpdfs(0);
    printf("%lld\n",dp[0]);
}
int main()
{
    sol();
    return 0;
}