Problem: http://www.spoj.com/problems/TREEPAL/
Here is my code:
include
include
using namespace std;
vector vec[100010],mp(100010);
bool vis[100010]{ 0 };
void dfs(int i, int floor) {
mp[floor]++;
vis[i] = 1;
for (int k = 0; k<vec[i].size(); ++k) {
if (!vis[vec[i][k]]) dfs(vec[i][k], floor + 1);
}
}
int findGCD(int a, int b)
{
return (b == 0) ? a : findGCD(b, a%b);
}
int main() {
//ios::sync_with_stdio(0);
//cin.tie(0);
int n;
int u, v;
while (cin >> n)
{
int temp = n*(n - 1)/2;
int ans = 0;
while (n-->1)
{
cin >> u >> v;
vec[u].push_back(v);
vec[v].push_back(u);
}
dfs(1, 1);
for (auto c : mp) ans += c*(c - 1)/2;
int fac = findGCD(temp, ans);
cout << ans / fac << "/" << temp / fac << "\n";
for (int i = 0; i<100010; ++i) vec[i].clear(),mp[i]=0,vis[i]=0;
}
}
Can someone tell me what's wrong with this code? Or is my algorithm wrong? Please help me,thank you!!