#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];
}
}
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)
{
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;
}
}
}
}
}
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());
if(y < m.size())
{
int t = *mlis[y].begin();
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();
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:141:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < m.size(); i++)
~~^~~~~~~~~~
minmaxtree.cpp:170:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < M.size(); i++)
~~^~~~~~~~~~
minmaxtree.cpp:201:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < m.size(); i++)
~~^~~~~~~~~~
minmaxtree.cpp:203:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i = 0; i < M.size(); i++)
~~^~~~~~~~~~
minmaxtree.cpp:212:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(y < m.size())
~~^~~~~~~~~~
minmaxtree.cpp:110:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
minmaxtree.cpp:114: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:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &k);
~~~~~^~~~~~~~~~
minmaxtree.cpp:123: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 |
Incorrect |
13 ms |
9080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
256 ms |
28120 KB |
Output is correct |
| 2 |
Correct |
255 ms |
28120 KB |
Output is correct |
| 3 |
Correct |
307 ms |
28120 KB |
Output is correct |
| 4 |
Correct |
298 ms |
28848 KB |
Output is correct |
| 5 |
Correct |
220 ms |
28848 KB |
Output is correct |
| 6 |
Correct |
258 ms |
28848 KB |
Output is correct |
| 7 |
Correct |
237 ms |
28848 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
174 ms |
28848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
13 ms |
9080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
