给定一个 n 个点 n 条边的无向图,你需要求有多少种选择图上的一个点 p 和一条边 (x,y) 的方案,使得删去 (x,y) 后图变成一棵树,且这棵树以 p 为根时每个节点的儿子个数均不超过 3。保证至少存在一种这样的方案。
Input
输入的第一行一个整数 n(2≤n≤105) 表示节点数,接下来 n 行每行两个整数 x,y(1≤x,y≤n) 描述图上的一条边。保证图中没有重边自环。
Output
输出一行一个正整数表示答案。
Input
6
1 2
1 3
1 4
1 5
1 6
2 3
Output
10
解析:
n个点n条边,所以该图就成一个环。只有将环中的一条边删去,该图才能变为一棵树。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const int N=2e6+10;
vector <int> g[N];
map <int,int> k;
int p[N];
int d[N];
bool vis[N];
vector <PII> q; //储存成环的边
int n;
void dfs(int u,int pa)
{p[u]=pa;vis[u]=1;for (auto v:g[u]){if (v==pa) continue;if (vis[v]==1&&q.size()==0) //当点 v 被再次遍历时,现在已经建成一个环了,就可以回溯将环中的每条边放入队列 q 中{q.push_back({u,v});while (p[u]!=v){q.push_back({u,p[u]});u=p[u];}q.push_back({u,p[u]});}if (vis[v]==1) continue; //走过的点,不用继续操作了,否则会死循环dfs(v,u);}
}
signed main()
{ios;cin>>n;for (int i=1;i<=n;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);d[u]++;d[v]++;}for (int i=1;i<=n;i++){k[d[i]]++; //记录度数相同的点的数量}//for (auto x:k) cout<<x.first<<" "<<x.second<<endl;dfs(1,0);//for (auto x:q) cout<<x.first<<" "<<x.second<<endl;int ans=0;for (auto x:q) //遍历每条要删掉的边{int du=d[x.first];int dv=d[x.second];k[du]--;k[dv]--;k[du-1]++;k[dv-1]++;int res=0;bool flag=0;for (auto y:k) //删除边后,再遍历每个点,判断能否成为根节点{int cnt=y.first;int s=y.second;if (cnt<=3) res +=s;if (cnt>=5&&s>0) flag=1; //既当不了根节点,也当不了儿子节点}if (flag==0) ans +=res;k[du]++; //还原k[dv]++;k[du-1]--;k[dv-1]--;}cout<<ans;return 0;
}