PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Shikhar Sharma
Tester: Manan Grover
Editorialist: Aman Dwivedi
DIFFICULTY:
Easy
PREREQUISITES:
Degree, Trees, Observation
PROBLEM:
In Chefland, there are N cities numbered from 1 to N. The cities are connected using N−1 roads such that there exists a path between all pairs of cities. In other words, the cities and roads forma a tree-structure
The roads of Chefland are not in good condition. Therefore, all the roads need to be destroyed. The cost of destroying a road between cities x and y is d_x⋅d_y, where d_x and d_y are the degrees of the cities x and y respectively.
Note that, the degree of a city is the number of roads connected to it before each destroy operation.
Chef wants to find the minimum cost to destroy all the roads. On calculating this cost once, he finds the process very interesting. Therefore, he does this for Q more independent queries.
In each query, a road is removed and another road is added. Find the minimum cost to destroy all roads initially, and after each query. It is guaranteed that after each query, all the cities are still connected and form a tree-structure.
EXPLANATION:
Since the given graph is tree, that means there is always going to be a leaf present in the graph. It makes sense to delete the edge which have leaf as one of the vertex. As the degree is never negative and when two terms are multiplied and one term is 1 then the total also gets lowered.
Now let’s say we have a node having degree d, what will be its contribution to the answer ?
Its simple as we are removing an edge in which one vertex is leaf it means every time we remove an edge from this node. It will contribute its degree to the answer and the degree will be reduced by 1 each time. Hence its total contribution will be:
We can simply say that the contribution by every node will be:
Hence the total contribution by all the nodes will be the summation of the individual contribution. But remember when we are removing the leaf node, we have already added that node contribution with the other node that is connected with it. But with the above formulae we are adding the contribution twice. Hence you need to remove that contribution which have been added twice.
This will happen (N-1) times as there are (N-1) edges. Hence our answer will be
Now let’s move to the query part.
-
Removed an edge between a and b.
The degree of a and the degree of b decreases by 1 when edge is removed. What will be the contribution that will be removed by these nodes. Let’ say the degree of a and b are d_a and d_b before the edge is removed. When the edge is removed the contribution of node will start from d_a-1 and d_b-1 but we have already added d_a and d_b. Hence we needed to remove d_a and d_b from our answer.
-
Edge is added between a and b.
The degree increases by 1 for both the edges. Hence the new degree of these nodes will be d_a+1 and d_b+1. As when we remove the edge which is connected to a or b, then d_a+1 or d_b+1 contribution will be added which we haven’t included in our answer. Hence add this into your answer.
TIME COMPLEXITY:
O(Q+N)
SOLUTIONS:
Author
#include<bits/stdc++.h>
using namespace std;
int main()
{
std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--)
{
int n,q,i;
cin>>n>>q;
long long int deg[n+5]={0};
int u,v;
for(i=0;i<n-1;i++)
{
cin>>u>>v;
deg[u]++;
deg[v]++;
}
long long int ans=0;
for(i=1;i<=n;i++)
{
ans+=(deg[i]*(deg[i]+1))/2;
}
ans-=n-1;
cout<<ans<<'\n';
int a,b;
for(i=0;i<q;i++)
{
cin>>a>>b>>u>>v;
long long int new_ans=ans-deg[a]-deg[b];
deg[a]--;
deg[b]--;
new_ans+=deg[u]+deg[v]+2;
deg[a]++;
deg[b]++;
cout<<new_ans<<'\n';
}
}
}
Tester
#include <bits/stdc++.h>
using namespace std;
long long readInt(long long l, long long r, char endd) {
long long x = 0;
long long cnt = 0;
long long fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if (g == endd) {
assert(cnt > 0);
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
void dfs(int x, int vis[], vector<int> gr[], int in[], int out[], int &cnt){
if(vis[x]){
return;
}
in[x] = cnt++;
vis[x] = 1;
for(int i = 0; i < gr[x].size(); i++){
dfs(gr[x][i], vis, gr, in, out, cnt);
}
out[x] = cnt++;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
long long t;
t = readInt(1, 10000, '\n');
long long ns = 0;
long long qs = 0;
while(t--){
long long n, q;
n = readInt(1, 100000, ' ');
q = readInt(1, 100000, '\n');
ns += n;
assert(ns <= 200000);
qs += n;
assert(qs <= 200000);
long long con[n + 1] = {};
set<pair<int, int>> ed;
vector<int> gr[n + 1];
for(long long i = 0; i < n - 1; i++){
long long u, v;
u = readInt(1, n, ' ');
v = readInt(1, n, '\n');
ed.insert({min(u,v),max(u,v)});
gr[u].push_back(v);
gr[v].push_back(u);
con[u]++;
con[v]++;
}
int in[n + 1], out[n + 1], vis[n + 1] = {};
int cnt = 0;
dfs(1, vis, gr, in, out, cnt);
for(int i = 1; i < n + 1; i++){
assert(vis[i]);
}
long long ans = 1 - n;
for(long long i = 1; i < n + 1; i++){
ans += (con[i] * (con[i] + 1)) / 2;
}
cout<<ans<<"\n";
while(q--){
long long a, b, c, d;
a = readInt(1, n, ' ');
b = readInt(1, n, ' ');
c = readInt(1, n, ' ');
d = readInt(1, n, '\n');
if(ed.find({min(a, b), max(a, b)}) == ed.end()){
assert(false);
}
if(in[b] < in[a] && out[b] > out[a]){
swap(a, b);
}
if(in[b] <= in[c] && out[b] >= out[c]){
assert(in[b] > in[d] || out[b] < out[d]);
}else{
assert(in[b] <= in[d] && out[b] >= out[d]);
}
long long temp = ans - con[a] - con[b];
con[a]--;
con[b]--;
temp += con[c] + con[d] + 2;
con[a]++;
con[b]++;
cout<<temp<<"\n";
}
}
return 0;
}
,