### KushagrJaiswal's blog

By KushagrJaiswal, history, 14 months ago,

I've taken the idea to solve this problem from here — https://codeforces.com/blog/entry/113465?#comment-1009818.

But, my solution is getting a TLE on test 11.

Here's my code -

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using std::cin;
using std::cout;
using std::vector;
using std::map;
using std::sort;
using std::pair;
using std::make_pair;

void calculate_values(const vector<vector<int>>&, vector<int>&,
map<vector<int>, int>&, int, int);
void find_ans(const vector<vector<int>>&, const vector<int>&, bool&, int, int,
int);

int main()
{
int t;
cin >> t;

while (t--)
{
int n;
cin >> n;

vector<vector<int>> graph(n);

for (int i = 0; i < (n - 1); ++i)
{
int u, v;
cin >> u >> v;

--u;
--v;

graph[u].push_back(v);
graph[v].push_back(u);
}

vector<int> values(n);
map<vector<int>, int> table_of_values;
calculate_values(graph, values, table_of_values, 0, -1);

bool ans = true;
find_ans(graph, values, ans, 0, -1, table_of_values.size());

cout << (ans ? "YES\n" : "NO\n");
}

return 0;
}

void calculate_values(const vector<vector<int>>& graph, vector<int>& values,
map<vector<int>, int>& table_of_values, int vertex,
int parent)
{
for (int child : graph[vertex])
if (child != parent)
calculate_values(graph, values, table_of_values, child, vertex);

vector<int> children_values;
for (int child : graph[vertex])
if (child != parent)
children_values.push_back(values[child]);
sort(children_values.begin(), children_values.end());

auto it = table_of_values.find(children_values);

if (it != table_of_values.end())
{
values[vertex] = it->second;
}

else
{
int value = table_of_values.size();
table_of_values[children_values] = value;
values[vertex] = value;
}
}

void find_ans(const vector<vector<int>>& graph, const vector<int>& values,
bool& ans, int vertex, int parent, int size)
{
int number_of_odd_occurrences = 0;
int new_vertex;

{
vector<pair<int, int>> parities(size, make_pair(0, 0));

for (int child : graph[vertex])
{
if (child != parent)
{
parities[values[child]].first ^= 1;
parities[values[child]].second = child;
}
}

for (int i = 0; i < size; ++i)
{
if (parities[i].first == 1)
{
++(number_of_odd_occurrences);
new_vertex = (parities[i].second);
}
}

if (number_of_odd_occurrences >= 2)
{
ans = false;
return;
}
}

if (number_of_odd_occurrences == 1)
{
find_ans(graph, values, ans, new_vertex, vertex, size);
}
}


Can someone please tell me how to improve my code?

• 0

By KushagrJaiswal, history, 16 months ago,

My solution gets a wrong answer verdict, but I can't think of a counterexample.

Here's my solution — https://codeforces.com/contest/1772/submission/190133399. I have used 0-indexing, and have set the extra last element of the input to +inf in order to avoid bounds checking.

Can anyone give me a counterexample?

• +1