Kundu and Tree
<all possible pair in the tree b/w which(path ) there is atleast 2 red edge >
Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(
r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to cand vertex c to a . Note that (a,b,c), (b,a,c) and all such permutations will be considered as the same triplet.
If the answer is greater than 109 + 7, print the answer modulo (%) 109 + 7.
Input Format
The first line contains an integer N, i.e., the number of vertices in tree.
The next N-1 lines represent edges: 2 space separated integers denoting an edge followed by a color of the edge. A color of an edge is denoted by a small letter of English alphabet, and it can be either red(
The first line contains an integer N, i.e., the number of vertices in tree.
The next N-1 lines represent edges: 2 space separated integers denoting an edge followed by a color of the edge. A color of an edge is denoted by a small letter of English alphabet, and it can be either red(
r) or black(b).
Output Format
Print a single number i.e. the number of triplets.
Print a single number i.e. the number of triplets.
Constraints
1 ≤ N ≤ 105
A node is numbered between 1 to N.
1 ≤ N ≤ 105
A node is numbered between 1 to N.
Sample Input
5
1 2 b
2 3 r
3 4 r
4 5 b
Sample Output
4
Explanation
Given tree is something like this.
(2,3,4) is one such triplet because on all paths i.e 2 to 3, 3 to 4 and 2 to 4 there is atleast one edge having red color.
(2,3,5), (1,3,4) and (1,3,5) are other such triplets.
Note that (1,2,3) is NOT a triplet, because the path from 1 to 2 does not have an edge with red color.
(2,3,5), (1,3,4) and (1,3,5) are other such triplets.
Note that (1,2,3) is NOT a triplet, because the path from 1 to 2 does not have an edge with red color.
-------------------------------editorial---------------------------------------
This problem is solely based on following observations.
If there is a red edge between vertex 'a' and 'b' then if we delete the red edge then vertex a and b will lie on different comonenet of the tree. So, if we delete all of the red edges in the tree. All the three vertices i.e. a, b and c will have to lie of different disconnected components.
So, when you are scanning the tree and got that color of some edge is red, don't scan it and make forest i.e. disconnected tree.
Consider that size of these components are a1, a2, a3,.... , ak.
So, when you are scanning the tree and got that color of some edge is red, don't scan it and make forest i.e. disconnected tree.
Consider that size of these components are a1, a2, a3,.... , ak.
So we have to pick three vertices out of given k disconnected component which can be done in Snumber of ways.
S = 0;
for(i=1 ; i<= k ; i++)
for(j=i+1 ; j<= k; j++)
for(t=j+1 ; t<= k ; t++)
S += a[i]*a[j]*a[t];
return S%(10^9+7
But again as the value of k can be as large as N the given code will not work so there is a magical way to fine product of all possible triplets in o(n):P, So you have to calculate value of S in O(N) time. Which can be calculated using some observation. See setter's code for the value of S. :)
----------------------------------------dfs solution---------------------------------
Problem Setter's code :
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define s(a) scanf("%d",&a);
vector<int> edges[100009];
long long int visited[100009];
long long int count1[100009];
long long int B[100009],C[100009],D[100009];
void dfs(int x, int temp)
{
if(visited[x] == 0)
visited[x] = temp;
for(int i = 0 ; i< edges[x].size() ; i++)
{
if(visited[edges[x][i]] == 0)
dfs(edges[x][i],temp);
}
return;
}
int main()
{
int n,i,a,b;
char c;
s(n);
for(i=0 ; i< n -1 ; i++)
{
s(a);
s(b);
cin>>c;
if( c != 'r')
{
edges[a].push_back(b);
edges[b].push_back(a);
}
}
int temp = 1;
for(i=1 ; i<=n ; i++)
{
if(visited[i] == 0)
{
dfs(i,temp);
temp++;
}
}
for(i=1 ; i<= n ; i++)
count1[visited[i]]++;
long long int sum = 0;
B[n-1] = count1[n];
for(i=n-2;i>=0;i--) B[i] = (B[i+1] + count1[i+1])%MOD;
for(i=1;i<n-1;i++) C[i] = (count1[i+1]*B[i+1])%MOD;
D[n-2] = C[n-2];
for(i=n-3;i>=1;i--) D[i] = (D[i+1] + C[i])%MOD;
for(i=0;i<n-2;i++) sum = (sum + count1[i+1]*D[i+1])%MOD;
cout<< ( MOD + sum )%MOD<<endl;
return 0;
}
------------------------------------------union find solution-------------------
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int abcd[100010];
int parent[100010];
typedef long long int lli;
#define mod 1000000007
long long int B[100009],C[100009],D[100009];
#define MOD 1000000007
int find(int node)
{
int k;
if(parent[node]==node)
{
return node;
}
else
k= find(parent[node]);
return k;
}
void merge(int a, int b)
{
int x=find(a);
int y=find(b);
if(abcd[x]>abcd[y])
{
parent[y]=x;
abcd[x]+=abcd[y];
abcd[y]=0;
//cout<<" merging "<<a<<" b "<<b<<" as a common parent "<<x<<" abcd y "<<abcd[y]<<" abcd x "<<abcd[x]<<endl;
}
else
{
parent[x]=y;
abcd[y]+=abcd[x];
abcd[x]=0;
//cout<<" merging "<<a<<" b "<<b<<" as a common parent "<<y<<" abcd y "<<abcd[y]<<" abcd x "<<abcd[x]<<endl;
}
}
int main()
{
int n;
cin>>n;
for(int i=0;i<=n+1;i++)
{
parent[i]=i;
abcd[i]=1;
}
for(int i=0;i<n-1;i++)
{
int a,b;
char c;
cin>>a>>b>>c;
if(c=='r') continue;
else
{
if(find(a)!=find(b))
{
// cout<<" merging "<<a<<" "<<b<<endl;
merge(a,b);
}
}
}
vector<lli>count1;
for(int i=0;i<=n;i++) count1.push_back(0);
for(int i=1;i<=n;i++)
{
if(abcd[i]!=0)
{
count1[i]=(abcd[i]);// size of all sets
}
}
//*/**** jadu way to calculate product of all possible triplets in 4*o(n)*/
B[n-1] = count1[n];
int i;
for(i=n-2;i>=0;i--) B[i] = (B[i+1] + count1[i+1])%MOD;
for(i=1;i<n-1;i++) C[i] = (count1[i+1]*B[i+1])%MOD;
D[n-2] = C[n-2];
for(i=n-3;i>=1;i--) D[i] = (D[i+1] + C[i])%MOD;
lli sum=0;
for(i=0;i<n-2;i++) sum = (sum + count1[i+1]*D[i+1])%MOD;
cout<< ( MOD + sum )%MOD<<endl;
/*** jadu end*/////////////
return 0;
}
--------------------------------------union find solution with o(n^3) -- gives tle----
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int abcd[100010];
int parent[100010];
typedef long long int lli;
#define mod 1000000007
int find(int node)
{
int k;
if(parent[node]==node)
{
return node;
}
else
k= find(parent[node]);
return k;
}
void merge(int a, int b)
{
int x=find(a);
int y=find(b);
if(abcd[x]>abcd[y])
{
parent[y]=x;
abcd[x]+=abcd[y];
abcd[y]=0;
//cout<<" merging "<<a<<" b "<<b<<" as a common parent "<<x<<" abcd y "<<abcd[y]<<" abcd x "<<abcd[x]<<endl;
}
else
{
parent[x]=y;
abcd[y]+=abcd[x];
abcd[x]=0;
//cout<<" merging "<<a<<" b "<<b<<" as a common parent "<<y<<" abcd y "<<abcd[y]<<" abcd x "<<abcd[x]<<endl;
}
}
int main()
{
int n;
cin>>n;
for(int i=0;i<=n+1;i++)
{
parent[i]=i;
abcd[i]=1;
}
for(int i=0;i<n-1;i++)
{
int a,b;
char c;
cin>>a>>b>>c;
a-=1;
b-=1;
if(c=='r') continue;
else
{
if(find(a)!=find(b))
{
// cout<<" merging "<<a<<" "<<b<<endl;
merge(a,b);
}
}
}
vector<lli> dis_comp;
for(int i=0;i<n;i++)
{
if(abcd[i]!=0)
{
dis_comp.push_back(abcd[i]);
}
}
int siz=dis_comp.size();
// for(int i=0;i<n;i++) cout<<abcd[i]<<" ";
// cout<<endl;
// cout<<" size of disconnected components are "<<endl;
/* for(int i=0;i<siz;i++)
cout<<dis_comp[i]<<" ";
cout<<endl;*/
lli ans=0;
for(int i=0;i<siz;i++)
{
for(int j=i+1;j<siz;j++)
{
for(int k=j+1;k<siz;k++)
{
ans=(ans+((dis_comp[i]*dis_comp[j])%mod*dis_comp[k])%mod)%mod;
}
}
}
cout<<ans<<endl;
return 0;
}
No comments:
Post a Comment