网络游戏推广,淄博优化网站,中国有几家网络公司,如何制作自己的网站页制作基环树其实并不是树#xff0c;是指有n个点n条边的图#xff0c;我们知道n个点n-1条边的连通图是树#xff0c;再加一条边就会形成一个环#xff0c;所以基环树中一定有一个环#xff0c;长下面这样#xff1a; 由基环树可以引申出基环内向树和基环外向树
基环内向树如…基环树其实并不是树是指有n个点n条边的图我们知道n个点n-1条边的连通图是树再加一条边就会形成一个环所以基环树中一定有一个环长下面这样 由基环树可以引申出基环内向树和基环外向树
基环内向树如下特点是每个点的出度为1 基环内向树如下特点是每个点的入度为1 下面放点题做到相关题目随时更新
基环树组合数学
CF 1454E Number of Simple Paths
先记录环上的点每个环上的点引出去的子树中两点之间都只有一条路径然后子树和其他点之间都有两条路径因为有个环可以循环计算每个子树答案累加即可
#include bits/stdc.husing namespace std;typedef pairint, int PII;#define int long longvoid solve()
{int n;cin n;vectorvectorint g(n 1);vectorint in(n 1);for (int i 0 ;i n; i ){int a, b;cin a b;g[a].push_back(b);g[b].push_back(a);in[a] , in[b] ;}queueint q;for (int i 1; i n; i ) {if (in[i] 1) q.push(i);}while (q.size()){auto t q.front();q.pop();for (int i 0; i g[t].size(); i ){int j g[t][i];in[j] -- ;if (in[j] 1) q.push(j);}}vectorint huan;vectorint st(n 1);for (int i 1; i n; i ){if (in[i] 1){huan.push_back(i);st[i] true;}}int ans 0, sumtmp, sum 0;vectorbool visited(n 1);functionvoid(int, int) dfs [](int u, int fa){sumtmp ;if (visited[u]) return;visited[u] true;for (int i 0; i g[u].size(); i ){int j g[u][i];if (j fa || visited[j] || st[j]) continue;dfs(j, u);}return;};for (auto i : huan){sumtmp 0;dfs(i, -1);ans sumtmp * (sumtmp - 1) / 2;ans (sumtmp - 1) * (n - sumtmp - sum) * 2;sum sumtmp - 1;}ans huan.size() * (huan.size() - 1);cout ans \n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;cin t;while (t -- ){solve();}
}基环内向树dfs
牛客 寒假集训1K 牛镇公务员考试
基环内向树准确的说应该是森林
编号 i 向 a[i] 连边表示对其限制我们可以发现环之外的链对答案没什么影响因为确定了环上一点可以倒推出链上的所有答案原因就是约束关系所以我们在环上任取一点枚举这个点的五种答案然后遍历一下环看这个答案是否合法
因为不保证联通所以需要遍历每一个点
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;const int N 1000010;
const int maxn 1e6 1;
const int mod 998244353;void solve()
{int n;cin n;vectorint a(n 1);vectorstring s(n 1);for (int i 1; i n; i ) cin a[i] s[i];vectorbool st(n 1);int ans 1;for (int i 1; i n; i ){if (st[i]) continue;int j i;vectorint huan;for (; !st[j]; j a[j]){huan.push_back(j);st[j] true;}auto iter find(huan.begin(), huan.end(), j);if (iter huan.end()) continue;huan {iter, huan.end()};int tmp 0;for (int k 0; k 5; k ){int h k;for (auto t : huan) h (int)(s[t][h] - A);tmp h k;}ans ans * tmp % mod;}cout ans \n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t -- ){solve();}
}
