公司的网站,2023年新闻热点事件,稿定设计网站官网,wordpress 修改头像大小链接#xff1a;https://ac.nowcoder.com/acm/contest/18072/E 题目#xff1a;给你一棵n个节点的带标号无根树。每次#xff0c;你可以选择一个度数为1的节点并将它从树上移除。问总共有多少种不同的方式能将这棵树删到只剩 1 个点。两种方式不同当且仅当至少有一步被删除的…链接https://ac.nowcoder.com/acm/contest/18072/E 题目给你一棵n个节点的带标号无根树。每次你可以选择一个度数为1的节点并将它从树上移除。问总共有多少种不同的方式能将这棵树删到只剩 1 个点。两种方式不同当且仅当至少有一步被删除的节点不同。
思路首先我们把他看成有根树来求解一般我们以1为根也就是说1结点是最后才去除的我们以dp【i】来表示去除i子树有多少种方式dp[i] v是i的儿子;每次统计完答案以后都要sizei-sizev很容易想到这个跟减的顺序是没有关系的。
现在我们统计完了有根树的值现在可以考虑来换根了我们考虑从x-y从x根转化到y根首先我们考虑一下回退在y根中 ,;
根据这两条公式已经可以进行换根我们还可以化简把dp1[y]约掉
代码
#include iostream
#include cstdio
#include fstream
#include algorithm
#include cmath
#include deque
#include vector
#include queue
#include string
#include cstring
#include map
#include stack
#include set
#include cstdlib
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define re register
#define lson rt1
#define rson rt1|1
#define lowbit(a) ((a)-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define rep(i,n) for(int i0;(i)(n);i)
#define rep1(i,n) for(int i1;(i)(n);i)
#define se second
#define scd(a) scanf(%d,a)
#define scdd(a,b) scanf(%d%d,a,b)
#define scddd(a,b,c) scanf(%d%d%d,a,b,c)
#define ac coutans\n
#define F(x) ((x)/3((x)%31?0:tb))
#define G(x) ((x)tb?(x)*31:((x)-tb)*32)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairll,ll pii;
int dx[4] {-1,1,0,0},dy[4] {0,0,1,-1};
const ll mod998244353;
const ll N 1e610;
const double eps 1e-4;
//const double piacos(-1);
int n;
vectorint g[N];
ll f[N],invf[N],inv[N];
ll dp[N];
ll son[N];
ll ans;
int c(int x,int y){return (((f[x]*invf[x-y])%mod)*invf[y])%mod;
}
void dfs(int u,int p){son[u]1;dp[u]1;for(int v:g[u]){if(vp) continue;dfs(v,u);son[u]son[v];}int sson[u]-1;for(int v:g[u]){if(vp) continue;dp[u](dp[u]*(c(s,son[v])*dp[v]%mod))%mod;s-son[v];}//coutu dp[u]endl;
}
void DP(int u,int p){ans(ansdp[u])%mod;for(int v:g[u]){if(vp) continue;dp[v]dp[u]*invf[son[v]-1]%mod*f[son[v]]%mod;dp[v]dp[v]*invf[n-son[v]]%mod;dp[v]dp[v]*f[n-1-son[v]]%mod;DP(v,u);}
}
void sovle(){cinn;f[0]f[1]invf[0]invf[1]inv[1]1;for(int i2;in;i){f[i](f[i-1]*i)%mod;inv[i](mod-mod/i)*inv[mod%i]%mod;invf[i]invf[i-1]*inv[i]%mod;}for(int i1;in;i){int x,y;cinxy;g[x].push_back(y);g[y].push_back(x);}dfs(1,0);//coutdp[1]endl;DP(1,0);coutans;
}
int main()
{
#ifdef LOCALfreopen(in.txt, r, stdin);
#elseint t1;// cint;while(t--) sovle();
#endif // LOCALreturn 0;
}
