A. 星际旅行
将所有的边拆成两条,问题变成去掉两条边,使得原图存在一条欧拉路径。注意新图中所有点的度数均为偶数,只需按照去掉任意2个自环、去掉任意1个自环和任意一条边、去掉两条有公共顶点的边进行讨论即可。注意图不连通的判断方式,不是点不连通,而是边不连通..
本应就是一道规律题吧..
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define ll long long int
4 #define lf double
5 const ll N=1e7+50;
6 inline void read(ll &ss)
7 {
8 ss=0;
9 ll cit=0;
10 char ch;
11 ch=getchar();
12 while((ch>'9') or (ch<'0'))
13 {
14 if(ch=='-') cit=1;
15 ch=getchar();
16 }
17 while((ch<='9') and (ch>='0'))
18 {
19 ss=(ss<<3)+(ss<<1)+(ch^48);
20 ch=getchar();
21 }
22 if(cit) ss=-ss;
23 }
24 ll n,m,ts,alls,num,ans,cnt;//num代表回环边的数量，cnt代表普通边的数量
25 ll vis[N],head[N],d[N];
26 struct Role{ ll u,v,w,nxt; } a[N*2];
27 inline void add(ll u,ll v)
28 {
29 a[++ts].u=u;
30 a[ts].v=v;
31 a[ts].nxt=head[u];
32 head[u]=ts;
33 }
34 void dfs(ll now)
35 {
36 vis[now]=1;
37 for(ll i=head[now];i;i=a[i].nxt)
38 {
39 if(!vis[a[i].v])
40 {
41 dfs(a[i].v);
42 }
43 }
44 }
45 signed main()
46 {
47 read(n); read(m);
48 ll u,v;
49 for(ll i=1;i<=m;i++)
50 {
51 read(u); read(v);
52 if(u==v) { num++; continue; }
53 d[u]++; d[v]++;
54 add(u,v); add(v,u);
55 }
56 cnt=m-num;
57 if(cnt==0) { putchar('0'); return 0;}
58 for(ll i=1;i<=n;i++) if(d[i]) { dfs(i);break; }
59 for(ll i=1;i<=n;i++) if(d[i] and vis[i]==0) { putchar('0'); return 0;}
60 ans+=((num-1)*num)/2;
61 for(ll i=1;i<=n;i++) ans+=(d[i]*(d[i]-1))/2;
62 ans+=num*cnt;
63 printf("%lld",ans);
64 return 0;
65 }
66 /*
67 5 4
68 1 2
69 1 3
70 1 4
71 1 5
72 */
73
A_code
B. 砍树
咕咕咕..
C. 超级树
考虑dp[i][j]表示一棵i-超级树,有j条点不重复的路径的方案数。考虑dp[i]对dp[i+1]的贡献:枚举左子树和右子树的路径条数l、r,记num=dp[i][l]*dp[i][r],则有
• 什么也不做 dp[i+1][l+r]+=num • 根自己作为一条新路径 dp[i+1][l+r+1]+=num • 根连接到左子树(或右子树)的某条路径上 dp[i+1][l+r]+=2*num*(l+r) • 根连接左子树和右子树的各一条路径 dp[i+1][l+r-1]+=2*num*l*r • 根连接左子树(或右子树)的两条路径 dp[i+1][l+r-1]+=num*(l*(l-1)+r*(r- 1)) 边界为dp[1][0]=dp[1][1]=1,答案为dp[k][1]。看起来第二维状态可能有2 k 那么大,但注意到从dp[i]转移到dp[i+1]时,路径的条数最多减少1条,因此第二维只有k个状态对最终的状态有影响,只dp这些状态即可 复杂度为 O(k^3) 1 #include<bits/stdc++.h>
2 using namespace std;
3 #define ll long long int
4 #define lf double
5 inline void read(ll &ss)
6 {
7 ss=0;
8 ll cit=0;
9 char ch;
10 ch=getchar();
11 while((ch>'9') or (ch<'0'))
12 {
13 if(ch=='-') cit=1;
14 ch=getchar();
15 }
16 while((ch<='9') and (ch>='0'))
17 {
18 ss=(ss<<3)+(ss<<1)+(ch^48);
19 ch=getchar();
20 }
21 if(cit) ss=-ss;
22 }
23 //什么也不做--1 根自己作为一条新路径--2 根与子树相连--3
24 //左与右相连--4 左/右自己相连--5
25 ll n,mod,num;
26 ll f[500][500];
27 signed main()
28 {
29 read(n); read(mod);
30 f[1][1]=1; f[1][0]=1;
31 for(ll i=0;i<=n;i++)
32 {
33 for(ll j=0;j<=n;j++)
34 {
35 for(ll l=0;l<=j;l++)
36 {
37 num=f[i][(j-l)]*f[i][l]%mod;
38 f[i+1][j]+=num; f[i+1][j]%=mod;
39 f[i+1][j+1]+=num; f[i+1][j+1]%=mod;
40 f[i+1][j]+=num*j*2; f[i+1][j]%=mod;
41 f[i+1][j-1]+=num*l*(j-l)*2; f[i+1][j-1]%=mod;
42 f[i+1][j-1]+=num*(l*(l-1)+(j-l)*(j-l-1)); f[i+1][j-1]%=mod;
43 }
44 }
45 }
46 printf("%lld",f[n][1]%mod);
47 return 0;
48 }
C_code
D. 求和
预处理出所有k次方和所有节点的深度，树上差分即可..
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define lf double
const ll N=300050;
const ll mod=998244353;
inline void read(ll &ss)
{
ss=0;
ll cit=0;
char ch;
ch=getchar();
while((ch>'9') or (ch<'0'))
{
if(ch=='-') cit=1;
ch=getchar();
}
while((ch<='9') and (ch>='0'))
{
ss=(ss<<3)+(ss<<1)+(ch^48);
ch=getchar();
}
if(cit) ss=-ss;
}
ll n,t,ts,m,maxn,ans,k;
ll fa[N][50];
ll dep[N],head[N],down[N][55],f[N][55];
struct Summary{ ll u,v,w,nxt; } a[N*2];
inline void add(ll u,ll v)
{
a[++ts].u=u;
a[ts].v=v;
a[ts].nxt=head[u];
head[u]=ts;
}
void dfs(ll now,ll dad,ll depth)
{
maxn=max(maxn,depth);
dep[now]=depth;
fa[now][0]=dad;
for(ll i=1;i<=t;i++)
{
if(fa[now][i-1]==0) break;
fa[now][i]=fa[fa[now][i-1]][i-1];
}
for(ll i=head[now];i;i=a[i].nxt)
{
if(a[i].v==dad) continue;
dfs(a[i].v,now,depth+1);
}
return ;
}
inline ll lca(ll x,ll y)
{
if(dep[x]<dep[y]) swap(x,y); //保证 x 在 y 的下面..
for(ll i=t;i>=0;i--)
{
if(dep[fa[x][i]]>=dep[y] and fa[x][i]!=0) x=fa[x][i];
} //使达到同一深度..
if(x==y) return x;
for(ll i=t;i>=0;i--)
{
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i]; y=fa[y][i];
}
}
return fa[x][0];
}
signed main()
{
read(n);
t=(ll)(log(n)/log(2))+1;
ll u,v,w;
for(ll i=1;i<=n-1;i++)
{
read(u); read(v);
add(u,v); add(v,u);
}
dfs(1,0,0);
for(ll i=1;i<=n;i++)
{
down[i][0]=1;
for(ll j=1;j<=51;j++)
{
down[i][j]=(down[i][j-1]*i)%mod;
f[i][j]=(f[i-1][j]+down[i][j])%mod;
}
}
read(m);
ll anor;
for(ll i=1;i<=m;i++)
{
read(u); read(v); read(k);
anor=lca(u,v);
//cout<<anor<<" depth:"<<dep[u]<<" "<<dep[v]<<" "<<dep[anor]<<endl;
//cout<<f[dep[u]][k]<<" "<<f[dep[v]][k]<<endl;
ans=f[dep[u]][k]+f[dep[v]][k]-2*f[dep[anor]][k]+down[dep[anor]][k];
ans=(ans+mod*mod)%mod;
printf("%lld\n",ans);
}
return 0;
}
/*
9
1 2
1 3
2 4
2 5
4 6
4 7
6 8
6 9
*/
D_code