In this HackerEarth Edge Strength (Lowe) problem solution Monk is given a tree rooted at node 1.The tree has N nodes and N – 1 edges. Each edge has some strength associated with it. The strength of an edge is determined by the number of pair of nodes which are connected with the help of that particular edge.
Alternatively consider all the paths between every pair of nodes and the strength of an edge will be equal to the number of paths in which that edge comes.
Monk wants to know the strength of each edge of the tree.
Note: Node pair (i,j) is same as node pair (j,i).
HackerEarth Edge Strength (Lowe) problem solution.
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll n;
vector<ll>v[100005];
ll subtree[100005],par[100005],vis[100005];
vector<pair<ll,ll> >edge;
void dfs(ll node)
{
vis[node]=1;
subtree[node]=1;
ll i,j;
for(i=0;i<v[node].size();i++)
{
j=v[node][i];
if(!vis[j])
{
par[j]=node;
dfs(j);
subtree[node]+=subtree[j];
}
}
}
int main()
{
//freopen("inp16.txt","r",stdin);
//freopen("out16.txt","w",stdout);
ll i,j,k,x,y;
cin>>n;
cin>>x>>y;
for(i=1;i<n;i++)
{
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
edge.push_back({x,y});
}
dfs(1);
for(i=0;i<edge.size();i++)
{
x=edge[i].first;
y=edge[i].second;
if(par[x]!=y)
swap(x,y);
cout<<(n-subtree[x])*subtree[x]<<"n";
}
return 0;
}
Second solution
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<int>v[100005];
int val[100005];
bool vis[100005];
void dfs(int u)
{
vis[u]=1;val[u]=1;
for(int i=0;i<v[u].size();i++)
{
if(!vis[v[u][i]])
{
dfs(v[u][i]);
val[u]+=val[v[u][i]];
}
}
}
int main()
{
int n;
cin>>n;
assert(n>=1 && n<=1e5);
vector<pair<int,int> >edge;
int row,col;cin>>row>>col;
for(int i=1;i<=row;i++)
{
int x,y;
cin>>x>>y;
assert(x>=1 && x<=n);
assert(y>=1 && y<=n);
assert(x!=y);
edge.push_back(make_pair(x,y));
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1);ll ans=0;
for(int i=0;i<edge.size();i++)
{
int a=edge[i].first,b=edge[i].second;
ll x=min(val[a],val[b]);
cout<<x*(n-x)<<"n";
}
return 0;
}