#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18 + 1;
int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w)
{
x++;
y++;
vector<vector<pair<int, int>>> g(n + 1);
for (int i = 0; i < n - 1; ++i)
{
u[i]++;
v[i]++;
g[u[i]].push_back({v[i], w[i]});
g[v[i]].push_back({u[i], w[i]});
}
vector<vector<ll>> cost(n + 1, vector<ll>(2));
function<void(int, int, int)> compute_cost = [&](int node, int parent, int qui)
{
for (auto i : g[node])
{
if (i.first != parent)
{
cost[i.first][qui] = cost[node][qui] + i.second;
compute_cost(i.first, node, qui);
}
}
};
compute_cost(x, 0, 0);
compute_cost(y, 0, 1);
function<int()> greedy = [&]()
{
set<tuple<int, int, int>> accesibile;
vector<vector<int>> viz(n + 1, vector<int>(2));
accesibile.insert({0, x, 0});
accesibile.insert({0, y, 1});
int ans = 0;
int left = k;
while (!accesibile.empty())
{
int adam, qui, byqui;
tie(adam, qui, byqui) = *accesibile.begin();
accesibile.erase(accesibile.begin());
if (adam > left)
{
break;
}
left -= adam;
ans++;
viz[qui][byqui] = true;
for (auto i : g[qui])
{
if (!viz[i.first][byqui])
{
accesibile.insert({cost[i.first][byqui], i.first, byqui});
}
}
}
return ans;
};
function<int(int)> solve_root = [&](int root)
{
vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(n + n + 1, vector<ll>(3, inf)));
vector<bool> important(n + 1);
vector<int> sz(n + 1);
function<void(int, int)> dfs_important = [&](int node, int parent)
{
if (node == x || node == y)
{
important[node] = true;
}
for (auto i : g[node])
{
if (i.first != parent)
{
dfs_important(i.first, node);
}
}
for (auto i : g[node])
{
if (i.first != parent)
{
important[node] = important[node] || important[i.first];
}
}
};
dfs_important(root, 0);
function<void(int, int)> dfs = [&](int node, int parent)
{
dp[node][1][0] = cost[node][0];
dp[node][1][1] = cost[node][1];
dp[node][2][2] = max(cost[node][0], cost[node][1]);
sz[node] = 1;
if (node == x)
{
dp[node][1][1] = inf;
}
if (node == y)
{
dp[node][1][0] = inf;
}
for (auto i : g[node])
{
if (i.first != parent)
{
dfs(i.first, node);
int maxleft = sz[node] + sz[node];
int maxright = sz[i.first] + sz[i.first];
for (int color = 0; color <= 2; ++color)
{
vector<ll> merged(maxleft + maxright + 1, inf);
for (int color2 = 0; color2 <= 2; ++color2)
{
if (color != color2 && color != 2)
{
continue;
}
for (int cntleft = 1; cntleft <= maxleft; ++cntleft)
{
for (int cntright = 1; cntright <= maxright; ++cntright)
{
merged[cntleft + cntright] = min(merged[cntleft + cntright], dp[node][cntleft][color] + dp[i.first][cntright][color2]);
}
}
}
for (int cnt = 1; cnt <= maxleft + maxright; ++cnt)
{
if (important[i.first])
{
dp[node][cnt][color] = merged[cnt];
}
else
{
dp[node][cnt][color] = min(dp[node][cnt][color], merged[cnt]);
}
}
}
sz[node] += sz[i.first];
}
}
};
dfs(root, 0);
for (int i = n + n; i >= 1; --i)
{
if (dp[root][i][2] <= k)
{
return i;
}
}
return 0;
};
int ans = greedy();
vector<int> lying;
function<void(int, int, vector<int>)> find_nodes = [&](int node, int parent, vector<int> curent)
{
curent.push_back(node);
if (node == y)
{
lying = curent;
}
for (auto i : g[node])
{
if (i.first != parent)
{
find_nodes(i.first, node, curent);
}
}
curent.pop_back();
};
find_nodes(x, 0, {});
sort(lying.begin(), lying.end(), [&](int x, int y)
{ return abs(cost[x][0] - cost[x][1]) < abs(cost[y][0] - cost[y][1]); });
for (int i = 0; i < min(inf,(int)lying.size()); ++i)
{
ans = max(ans, solve_root(lying[i]));
}
return ans;
}
Compilation message
closing.cpp: In function 'int max_score(int, int, int, ll, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:176:50: error: no matching function for call to 'min(const ll&, int)'
176 | for (int i = 0; i < min(inf,(int)lying.size()); ++i)
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from closing.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
230 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: template argument deduction/substitution failed:
closing.cpp:176:50: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
176 | for (int i = 0; i < min(inf,(int)lying.size()); ++i)
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from closing.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
278 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: template argument deduction/substitution failed:
closing.cpp:176:50: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
176 | for (int i = 0; i < min(inf,(int)lying.size()); ++i)
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from closing.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
3468 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: template argument deduction/substitution failed:
closing.cpp:176:50: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
176 | for (int i = 0; i < min(inf,(int)lying.size()); ++i)
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from closing.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
3474 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: template argument deduction/substitution failed:
closing.cpp:176:50: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
176 | for (int i = 0; i < min(inf,(int)lying.size()); ++i)
| ^
