#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'
using namespace std;
const int maxn = 70003;
const int maxlog = 20;
const int inf = 1e9;
struct chain
{
int a, b, w;
chain() {}
chain(int a, int b, int w)
{
this->a = a;
this->b = b;
this->w = w;
}
bool operator < (const chain &other) const
{
return w < other.w;
}
bool operator < (const int x) const
{
return w < x;
}
};
int n, k;
vector <int> adj[maxn];
vector <chain> vmin, vmax;
void read()
{
cin >> n;
for (int i = 1; i <= n-1; i++)
{
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
cin >> k;
for (int i = 1; i <= k; i++)
{
char type;
int a, b, w;
cin >> type >> a >> b >> w;
if (type == 'm')
vmin.push_back(chain(a, b, w));
else
vmax.push_back(chain(a, b, w));
}
}
int sz[maxn];
int par[maxn][maxlog];
void pre_dfs(int ver)
{
sz[ver] = 1;
for (auto i: adj[ver])
if (i != par[ver][0])
{
par[i][0] = ver;
pre_dfs(i);
sz[ver] += sz[i];
}
}
int pos[maxn], head[maxn];
vector <int> order;
void dfs(int ver, int curr_head)
{
order.push_back(ver);
pos[ver] = (int)order.size()-1;
head[ver] = curr_head;
int max_sz = -1, idx = -1;
for (auto i: adj[ver])
if (i != par[ver][0])
if (sz[i] > max_sz)
max_sz = sz[i], idx = i;
if (idx != -1)
dfs(idx, curr_head);
for (auto i: adj[ver])
if (i != par[ver][0] && i != idx)
dfs(i, i);
}
void precompute()
{
pre_dfs(1);
dfs(1, 1);
for (int j = 1; j < maxlog; j++)
for (int i = 1; i <= n; i++)
par[i][j] = par[par[i][j-1]][j-1];
}
bool is_upper(int a, int b)
{
return pos[a] <= pos[b] && pos[a] + sz[a] - 1 >= pos[b];
}
int lca(int a, int b)
{
if (is_upper(a, b))
return a;
for (int i = maxlog-1; i >= 0; i--)
if (par[a][i] && !is_upper(par[a][i], b))
a = par[a][i];
return par[a][0];
}
struct node
{
int min_val, max_val;
node() {min_val = inf, max_val = 0;}
};
node tr[maxn * 4];
void update(int v, int l, int r, int ll, int rr, int val, bool type)
{
if (l > rr || r < ll)
return;
if (l >= ll && r <= rr)
{
if (type)
tr[v].min_val = min(tr[v].min_val, val);
else
tr[v].max_val = max(tr[v].max_val, val);
return;
}
int mid = (l + r) / 2;
update(v * 2, l, mid, ll, rr, val, type);
update(v * 2 + 1, mid + 1, r, ll, rr, val, type);
}
int get_min(int v, int l, int r, int pos)
{
if (l == r)
return tr[v].min_val;
int mid = (l + r) / 2;
if (pos <= mid)
return min(tr[v].min_val, get_min(v * 2, l, mid, pos));
else
return min(tr[v].min_val, get_min(v * 2 + 1, mid + 1, r, pos));
}
int get_max(int v, int l, int r, int pos)
{
if (l == r)
return tr[v].max_val;
int mid = (l + r) / 2;
if (pos <= mid)
return max(tr[v].max_val, get_max(v * 2, l, mid, pos));
else
return max(tr[v].max_val, get_max(v * 2 + 1, mid + 1, r, pos));
}
void update_min(int a, int b, int w)
{
if (a == b)
return;
while (!is_upper(head[a], b))
{
update(1, 0, n-1, pos[head[a]], pos[a], w, true);
a = par[head[a]][0];
}
update(1, 0, n-1, pos[b]+1, pos[a], w, true);
}
void update_max(int a, int b, int w)
{
if (a == b)
return;
while (!is_upper(head[a], b))
{
update(1, 0, n-1, pos[head[a]], pos[a], w, false);
a = par[head[a]][0];
}
update(1, 0, n-1, pos[b]+1, pos[a], w, false);
}
int l[maxn], r[maxn];
bool is_valid(int ver, int a, int b)
{
int cnt = 0;
if (is_upper(ver, a))
cnt++;
if (is_upper(ver, b))
cnt++;
return cnt == 1;
}
vector <pair <int, int> > adj1[maxn];
int match[maxn];
int used[maxn];
int curr_time;
bool kuhn(int ver)
{
for (auto i: adj1[ver])
for (int j = i.first; j <= i.second; j++)
if (used[j] != curr_time)
{
if (j <= (int)vmin.size())
{
if (is_valid(ver, vmin[j-1].a, vmin[j-1].b))
{
used[j] = curr_time;
if (match[j] == -1 || kuhn(match[j]))
{
match[j] = ver;
return true;
}
}
}
else
{
if (is_valid(ver, vmax[j-1-(int)vmin.size()].a, vmax[j-1-(int)vmin.size()].b))
{
used[j] = curr_time;
if (match[j] == -1 || kuhn(match[j]))
{
match[j] = ver;
return true;
}
}
}
}
return false;
}
int ans[maxn];
void solve()
{
precompute();
sort (vmin.begin(), vmin.end());
sort (vmax.begin(), vmax.end());
for (auto i: vmin)
{
int curr_lca = lca(i.a, i.b);
update_max(i.a, curr_lca, i.w);
update_max(i.b, curr_lca, i.w);
}
for (auto i: vmax)
{
int curr_lca = lca(i.a, i.b);
update_min(i.a, curr_lca, i.w);
update_min(i.b, curr_lca, i.w);
}
for (int i = 2; i <= n; i++)
{
l[i] = get_max(1, 0, n-1, pos[i]);
r[i] = get_min(1, 0, n-1, pos[i]);
}
for (int i = 2; i <= n; i++)
{
int low = lower_bound(vmin.begin(), vmin.end(), l[i]) - vmin.begin();
int high = lower_bound(vmin.begin(), vmin.end(), r[i]) - vmin.begin();
if (high == (int)vmin.size() || vmin[high].w != r[i])
high--;
if (low <= high)
adj1[i].push_back({low + 1, high + 1});
low = lower_bound(vmax.begin(), vmax.end(), l[i]) - vmax.begin();
high = lower_bound(vmax.begin(), vmax.end(), r[i]) - vmax.begin();
if (high == (int)vmax.size() || vmax[high].w != r[i])
high--;
if (low <= high)
adj1[i].push_back({low + (int)vmin.size() + 1, high + (int)vmin.size() + 1});
}
memset(match, -1, sizeof(match));
memset(used, -1, sizeof(match));
for (int i = 2; i <= n; i++)
{
curr_time++;
kuhn(i);
}
memset(ans, -1, sizeof(ans));
for (int i = 1; i <= k; i++)
{
if (i <= (int)vmin.size())
ans[match[i]] = vmin[i-1].w;
else
ans[match[i]] = vmax[i-(int)vmin.size()-1].w;
}
for (int i = 2; i <= n; i++)
if (ans[i] == -1)
ans[i] = l[i];
for (int i = 2; i <= n; i++)
cout << i << " " << par[i][0] << " " << ans[i] << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
read();
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6636 KB |
Output is correct |
| 2 |
Correct |
5 ms |
6636 KB |
Output is correct |
| 3 |
Correct |
5 ms |
6656 KB |
Output is correct |
| 4 |
Correct |
5 ms |
6636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1072 ms |
21856 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1100 ms |
18240 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6636 KB |
Output is correct |
| 2 |
Correct |
5 ms |
6636 KB |
Output is correct |
| 3 |
Correct |
5 ms |
6656 KB |
Output is correct |
| 4 |
Correct |
5 ms |
6636 KB |
Output is correct |
| 5 |
Execution timed out |
1072 ms |
21856 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
