QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#309220 | #5439. Meet in the Middle | Rong7 | TL | 0ms | 0kb | C++14 | 7.3kb | 2024-01-20 15:46:23 | 2024-01-20 15:46:24 |
answer
// Not afraid to dark.
#include <bits/stdc++.h>
using namespace std;
#define int long long
namespace io {
int read_pos, read_dt; char read_char;
inline int read (int &p = read_pos){
p = 0, read_dt = 1; read_char = getchar ();
while (! isdigit (read_char)){
if (read_char == '-')
read_dt = - 1;
read_char = getchar ();
}
while (isdigit (read_char)){
p = (p << 1) + (p << 3) + read_char - 48;
read_char = getchar ();
}
return p = p * read_dt;
}
int write_sta[65], write_top;
inline void write (int x){
if (x < 0)
putchar ('-'), x = - x;
write_top = 0;
do
write_sta[write_top ++] = x % 10, x /= 10;
while (x);
while (write_top)
putchar (write_sta[-- write_top] + 48);
}
int llen;
inline int get_string (char c[], int &len = llen){
len = 0;
read_char = getchar ();
while (read_char == ' ' || read_char == '\n' || read_char == '\r')
read_char = getchar ();
while (read_char != ' ' && read_char != '\n' && read_char != '\r'){
c[++ len] = read_char;
read_char = getchar ();
}
return len;
}
}
#define log2_(x) (31 ^ __builtin_clz (x))
const int N = 2e5 + 5, LOG = 17;
int T, n, Q;
int idx, dfn[N << 1], rep[N << 1], dep[N << 1], st[LOG + 5][N << 1];
int d2[N], d1[N];
int firs[N], nex[N << 1], to[N << 1], w[N << 1], tot;
vector < pair < int , int > > gto[N];
inline void Add (int u, int v, int l){ // for Tree 1
++ tot;
nex[tot] = firs[u];
firs[u] = tot;
to[tot] = v;
w[tot] = l;
}
inline void Connect (int u, int v, int l){ // for Tree 1
gto[u].push_back (make_pair (v, l));
}
inline int get_mindep (int u, int v){ // for Tree 2
return dep[u] < dep[v] ? u : v;
}
inline int LCA_t2 (int u, int v){ // for Tree 2
u = dfn[u], v = dfn[v];
if (u > v)
swap (u, v);
int p = log2_ (v - u + 1);
return get_mindep (st[p][u], st[p][v - (1 << p) + 1]);
}
inline int dis2 (int u, int v){ // for Tree 2
int lca = LCA_t2 (u, v);
return d2[u] + d2[v] - (d2[lca] << 1);
}
inline void init1 (int u, int father){ // for Tree 2
dep[u] = dep[father] + 1;
rep[dfn[u] = ++ idx] = u;
st[0][dfn[u]] = u;
for (int e = firs[u], v;e;e = nex[e]){
v = to[e];
if (v == father)
continue;
d2[v] = d2[u] + w[e];
init1 (v, u);
rep[++ idx] = u;
st[0][idx] = u;
}
}
int ord[N], dfs[N], id, sz[N];
int ans[N << 2];
vector < pair < int , int > > Que[N];
void init2 (int u, int father){ // for Tree 1
ord[u] = ++ id;
dfs[id] = u;
sz[u] = 1;
for (auto e : gto[u]){
int v = e.first;
if (v == father)
continue;
d1[v] = d1[u] + e.second;
init2 (v, u);
sz[u] += sz[v];
}
}
namespace Sgt {
#define lson(p) ((p) << 1)
#define rson(p) ((p) << 1 | 1)
struct sgtree {
int l, r;
int a[2], b[2], tag;
sgtree (int _l = 0, int _r = 0){
l = _l;
r = _r;
a[0] = a[1] = b[0] = b[1] = tag = 0;
}
} tr[N << 2];
inline void put_tag (int p, int x){
tr[p].tag += x;
tr[p].b[0] += x;
tr[p].b[1] += x;
}
inline void push_up (int p){
int res = 0;
if (dis2 (tr[lson (p)].a[0], tr[lson (p)].a[1]) + tr[lson (p)].b[0] + tr[lson (p)].b[1] > res){
res = dis2 (tr[lson (p)].a[0], tr[lson (p)].a[1]) + tr[lson (p)].b[0] + tr[lson (p)].b[1];
tr[p].a[0] = tr[lson (p)].a[0];
tr[p].a[1] = tr[lson (p)].a[1];
tr[p].b[0] = tr[lson (p)].b[0];
tr[p].b[1] = tr[lson (p)].b[1];
}
if (dis2 (tr[rson (p)].a[0], tr[rson (p)].a[1]) + tr[rson (p)].b[0] + tr[rson (p)].b[1] > res){
res = dis2 (tr[rson (p)].a[0], tr[rson (p)].a[1]) + tr[rson (p)].b[0] + tr[rson (p)].b[1];
tr[p].a[0] = tr[rson (p)].a[0];
tr[p].a[1] = tr[rson (p)].a[1];
tr[p].b[0] = tr[rson (p)].b[0];
tr[p].b[1] = tr[rson (p)].b[1];
}
for (int i = 0;i < 2;++ i)
for (int j = 0;j < 2;++ j)
if (dis2 (tr[lson (p)].a[i], tr[rson (p)].a[j]) + tr[lson (p)].b[i] + tr[rson (p)].b[j] > res){
res = dis2 (tr[lson (p)].a[i], tr[rson (p)].a[j]) + tr[lson (p)].b[i] + tr[rson (p)].b[j];
tr[p].a[0] = tr[lson (p)].a[i];
tr[p].b[0] = tr[lson (p)].b[i];
tr[p].a[1] = tr[rson (p)].a[j];
tr[p].b[1] = tr[rson (p)].b[j];
}
}
inline void push_down (int p){
if (tr[p].tag){
put_tag (lson (p), tr[p].tag);
put_tag (rson (p), tr[p].tag);
tr[p].tag = 0;
}
}
inline void Build (int p, int l, int r){
tr[p].l = l;
tr[p].r = r;
if (l == r){
tr[p].a[0] = tr[p].a[1] = dfs[l];
tr[p].b[0] = tr[p].b[1] = d1[dfs[l]];
tr[p].tag = 0;
return ;
}
int mid = (l + r) >> 1;
Build (lson (p), l, mid);
Build (rson (p), mid + 1, r);
push_up (p);
}
inline void Update (int p, int l, int r, int x){
if (l > r)
return ;
if (l <= tr[p].l && tr[p].r <= r){
put_tag (p, x);
return ;
}
push_down (p);
int mid = (tr[p].l + tr[p].r) >> 1;
if (l <= mid)
Update (lson (p), l, r, x);
if (r > mid)
Update (rson (p), l, r, x);
push_up (p);
}
} using namespace Sgt;
void Solve (int u, int father){
for (auto x : Que[u])
ans[x.second] = max (dis2 (tr[1].a[0], x.first) + tr[1].b[0], dis2 (tr[1].a[1], x.first) + tr[1].b[1]);
for (auto e : gto[u]){
int v = e.first, we = e.second;
if (v == father)
continue;
Update (1, 1, ord[v] - 1, we);
Update (1, ord[v] + sz[v], n, we);
Update (1, ord[v], ord[v] + sz[v] - 1, - we);
Solve (v, u);
Update (1, 1, ord[v] - 1, - we);
Update (1, ord[v] + sz[v], n, - we);
Update (1, ord[v], ord[v] + sz[v] - 1, we);
}
}
signed main (){
io::read (T);
io::read (n), io::read (Q);
for (int i = 1, u, v, l;i < n;++ i){
io::read (u), io::read (v), io::read (l);
Connect (u, v, l);
Connect (v, u, l);
}
for (int i = 1, u, v, l;i < n;++ i){
io::read (u), io::read (v), io::read (l);
Add (u, v, l);
Add (v, u, l);
}
init1 (1, 0);
for (int i = 1;i <= LOG;++ i)
for (int j = 1;j <= idx;++ j){
st[i][j] = st[i - 1][j];
if (j + (1 << (i - 1)) <= idx)
st[i][j] = get_mindep (st[i][j], st[i - 1][j + (1 << (i - 1))]);
}
init2 (1, 0);
Build (1, 1, n);
for (int i = 1, u, v;i <= Q;++ i){
io::read (u), io::read (v);
Que[u].push_back (make_pair (v, i));
}
Solve (1, 0);
for (int i = 1;i <= Q;++ i)
io::write (ans[i]), puts ("");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3 4 1 2 1 2 3 2 1 2 2 2 3 1 1 1 1 2 2 1 2 2