#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>
using namespace std;
vector<int> arr[70010];
int par[70010][18];
int dep[70010];
void f(int x, int p)
{
par[x][0] = p;
for(int i = 1; i < 18; i++)
par[x][i] = par[par[x][i - 1]][i - 1];
for(int y : arr[x])
{
if(y == p)
continue;
dep[y] = dep[x] + 1;
f(y, x);
}
}
int lca(int x, int y)
{
if(dep[y] > dep[x])
swap(x, y);
int t = dep[x] - dep[y];
for(int i = 0; i < 18; i++)
if(t & (1 << i))
x = par[x][i];
if(x == y)
return x;
for(int i = 17; i >= 0; i--)
{
if(par[x][i] != par[y][i])
{
x = par[x][i];
y = par[y][i];
}
}
assert(x != y);
assert(par[x][0] == par[y][0]);
return par[x][0];
}
struct uf
{
int upar[70010];
int root(int x)
{
return x == upar[x] ? x : (upar[x] = root(upar[x]));
}
bool merge(int x, int y)
{
assert(x != 1 && y != 1);
x = root(x);
y = root(y);
if(x == y)
return 0;
if(dep[x] < dep[y])
upar[y] = x;
else
upar[x] = y;
return 1;
}
};
struct str
{
int x, y, z;
bool operator <(const str &a) const
{
return z < a.z;
}
};
vector<str> m, M;
uf muf, Muf;
int midx[70010];
int Midx[70010];
set<int> mlis[70010];
set<int> Mlis[70010];
int res[70010];
int main()
{
//freopen("in", "r", stdin);
//freopen("out", "w", stdout);
int n, k, i, j;
scanf("%d", &n);
for(i = 0; i < n - 1; i++)
{
int x, y;
scanf("%d%d", &x, &y);
arr[x].push_back(y);
arr[y].push_back(x);
}
scanf("%d", &k);
for(i = 0; i < k; i++)
{
char c;
int x, y, z;
scanf(" %c%d%d%d", &c, &x, &y, &z);
if(c == 'm')
m.push_back({ x, y, z });
else
M.push_back({ x, y, z });
}
memset(midx, -1, sizeof midx);
memset(Midx, -1, sizeof Midx);
dep[1] = 0;
f(1, 1);
for(i = 1; i <= n; i++)
muf.upar[i] = Muf.upar[i] = i;
sort(m.rbegin(), m.rend());
sort(M.begin(), M.end());
for(i = 0; i < m.size(); i++)
{
int r = lca(m[i].x, m[i].y);
for(j = 0; j < 2; j++)
{
int x = (j == 0) ? m[i].x : m[i].y;
while(dep[x] > dep[r])
{
if(midx[x] == -1)
{
mlis[i].insert(x);
midx[x] = i;
}
while(1)
{
x = muf.root(x);
int t = par[x][0];
if(midx[t] != -1)
muf.merge(x, t);
else
{
x = t;
break;
}
}
}
}
}
for(i = 0; i < M.size(); i++)
{
int r = lca(M[i].x, M[i].y);
for(j = 0; j < 2; j++)
{
int x = (j == 0) ? M[i].x : M[i].y;
while(dep[x] > dep[r])
{
if(Midx[x] == -1)
{
Mlis[i].insert(x);
Midx[x] = i;
}
while(1)
{
x = Muf.root(x);
int t = par[x][0];
if(Midx[t] != -1)
Muf.merge(x, t);
else
{
x = t;
break;
}
}
}
}
}
for(i = 1; i <= n; i++)
assert(midx[i] == -1 || Midx[i] == -1 || m[midx[i]].z < M[Midx[i]].z);
set<pair<int, int>> s;
for(i = 0; i < m.size(); i++)
s.insert({ (int)mlis[i].size(), i });
for(i = 0; i < M.size(); i++)
s.insert({ (int)Mlis[i].size(), (int)(i + m.size()) });
while(!s.empty())
{
int x, y;
tie(x, y) = *s.begin();
s.erase(s.begin());
assert(x >= 1);
if(y < m.size())
{
int t = *mlis[y].begin();
assert(res[t] == 0);
res[t] = m[y].z;
for(int z : mlis[y])
{
if(Midx[z] == -1)
continue;
s.erase({ (int)Mlis[Midx[z]].size(), (int)(Midx[z] + m.size()) });
Mlis[Midx[z]].erase(z);
s.insert({ (int)Mlis[Midx[z]].size(), (int)(Midx[z] + m.size()) });
}
}
else
{
y -= m.size();
int t = *Mlis[y].begin();
assert(res[t] == 0);
res[t] = M[y].z;
for(int z : Mlis[y])
{
if(midx[z] == -1)
continue;
s.erase({ (int)mlis[midx[z]].size(), midx[z] });
mlis[midx[z]].erase(z);
s.insert({ (int)mlis[midx[z]].size(), midx[z] });
}
}
}
for(i = 2; i <= n; i++)
{
if(res[i] == 0)
{
if(midx[i] != -1)
res[i] = m[midx[i]].z;
else if(Midx[i] != -1)
res[i] = M[Midx[i]].z;
}
}
for(i = 2; i <= n; i++)
printf("%d %d %d\n", i, par[i][0], res[i]);
return 0;
}
Compilation message
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:144:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < m.size(); i++)
~~^~~~~~~~~~
minmaxtree.cpp:173:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < M.size(); i++)
~~^~~~~~~~~~
minmaxtree.cpp:207:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < m.size(); i++)
~~^~~~~~~~~~
minmaxtree.cpp:209:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < M.size(); i++)
~~^~~~~~~~~~
minmaxtree.cpp:219:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(y < m.size())
~~^~~~~~~~~~
minmaxtree.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
minmaxtree.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
minmaxtree.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &k);
~~~~~^~~~~~~~~~
minmaxtree.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c%d%d%d", &c, &x, &y, &z);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
24 ms |
18040 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
305 ms |
36920 KB |
Output is correct |
| 2 |
Correct |
243 ms |
36920 KB |
Output is correct |
| 3 |
Correct |
242 ms |
36920 KB |
Output is correct |
| 4 |
Correct |
288 ms |
37728 KB |
Output is correct |
| 5 |
Correct |
281 ms |
37728 KB |
Output is correct |
| 6 |
Correct |
249 ms |
37728 KB |
Output is correct |
| 7 |
Correct |
200 ms |
37728 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
152 ms |
42492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
24 ms |
18040 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
