Link do zadania: https://szkopul.edu.pl/problemset/problem/jgCcEjQu3kdpM4BmxA6GujfX/site/?key=statement
Mój program działa podobnie jak wzorcówka, z tym że idzie od korzenia do liści zamiast odwrotnie. Mimo tego, że nie znalazłem żadnego przypadku gdzie by nie działał to i tak daje 30pkt. Jeśli ktoś znalazł jakiś przykład, w którym mój kod nie zadziała to bardzo by mi to pomogło.
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <queue>
#include <fstream>
#include <cmath>
#include<bitset>
#include <array>
#include <stack>
#include<iomanip>
#include <deque>
using namespace std;
using ll = long long;
using ld = long double;
const ll mod1 = 998244353;
const ll mod2 = 1e9 + 7;
const int MAXN = 3e5 + 222;
const int K = 27;
const ll pp = 307;
const int ZERO = 1e5;
ll n,lim,flag;
vector<int> adj[MAXN];
ll dp[MAXN];
void dfs(int v, int p)
{
ll children = adj[v].size()-1 + (v==1);
dp[v] += lim;
dp[v] = min((ll)n, dp[v]);
if (dp[v] < children)
flag = 1;
ll rem = dp[v] - children;
for (auto u : adj[v])
{
if (u == p)continue;
dp[u] += rem;
dfs(u, v);
}
}
bool check(ll x)
{
fill(dp, dp + n + 3, 0);
lim = x;
flag = 0;
dfs(1, 1);
//cout<<flag<<endl;
return !flag;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
ll l = 0, r = 3e5;
while (l < r)
{
ll m = (l + r) / 2;
if (check(m))
r = m;
else
l = m + 1;
}
cout << l << '\n';
return 0;
}