QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#696171 | #5439. Meet in the Middle | Code_quantum | TL | 0ms | 0kb | C++14 | 4.9kb | 2024-10-31 21:43:10 | 2024-10-31 21:43:10 |
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
#define il inline
#define pb push_back
#define px first
#define py second
const int inf = 1e18;
const int N = 100005;
const int M = 500005;
struct node{int sum, l, r, ld, rd;};
il bool operator < (const node &r1, const node &r2){return r1.sum < r2.sum;}
int n, q, lg[N * 2], ans[M];
vector<pii> vq[N];
struct TREE{
struct edges{int to, next, w;}; edges edge[N * 2];
int cnt, idx, tidx, sz[N], ret[N], dfn[N], dep[N], pre[N], tdfn[N], head[N], st[N * 2][19];
il void add_edge(int u, int v, int w){
edge[++ cnt].to = v; edge[cnt].next = head[u]; edge[cnt].w = w; head[u] = cnt;
}
void dfs(int u, int fa){
st[tdfn[u] = ++ tidx][0] = u; ret[dfn[u] = ++ idx] = u;
dep[u] = dep[fa] + 1; sz[u] = 1;
for(int v, w, i = head[u]; ~ i; i = edge[i].next){
v = edge[i].to; w = edge[i].w; if(v == fa) continue;
pre[v] = pre[u] + w; dfs(v, u); st[++ tidx][0] = u; sz[u] += sz[v];
}
}
il int getlca(int x, int y){
if(x == y) return x; if(! x || ! y) return 0;
x = tdfn[x]; y = tdfn[y]; if(x > y) swap(x, y);
int k = lg[y - x + 1]; int l = st[x][k], r = st[y - (1 << k) + 1][k];
return dep[l] < dep[r] ? l : r;
}
il int getdis(int x, int y){
return pre[x] + pre[y] - 2ll * pre[getlca(x, y)];
}
void init(){
cnt = idx = tidx = 0;
for(int i = 1; i <= n; i ++){
head[i] = -1; tdfn[i] = dfn[i] = dep[i] = sz[i] = ret[i] = pre[i] = 0;
for(int k = 0; k <= 18; k ++) st[i][k] = 0;
}
for(int i = 1; i < n; i ++){
int u, v, w; scanf("%lld %lld %lld", &u, &v, &w);
add_edge(u, v, w); add_edge(v, u, w);
}
dfs(1, 0);
for(int k = 1; k <= 18; k ++) for(int i = 1; i + (1 << k) - 1 <= tidx; i ++){
int l = st[i][k - 1], r = st[i + (1 << (k - 1))][k - 1];
st[i][k] = dep[l] < dep[r] ? l : r;
}
}
};
TREE t1, t2;
namespace sgtree{
#define lc (x << 1)
#define rc (x << 1 | 1)
struct segtree{
int l, r, tag; node dia;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define tag(x) tree[x].tag
#define dia(x) tree[x].dia
};
segtree tree[N << 2];
il void pushup(int x){
dia(x) = max(dia(lc), dia(rc));
dia(x) = max(dia(x), (node){t2.getdis(dia(lc).l, dia(rc).l) + dia(lc).ld + dia(rc).ld, dia(lc).l, dia(rc).l, dia(lc).ld, dia(rc).ld});
dia(x) = max(dia(x), (node){t2.getdis(dia(lc).l, dia(rc).r) + dia(lc).ld + dia(rc).rd, dia(lc).l, dia(rc).r, dia(lc).ld, dia(rc).rd});
dia(x) = max(dia(x), (node){t2.getdis(dia(lc).r, dia(rc).l) + dia(lc).rd + dia(rc).ld, dia(lc).r, dia(rc).l, dia(lc).rd, dia(rc).ld});
dia(x) = max(dia(x), (node){t2.getdis(dia(lc).r, dia(rc).r) + dia(lc).rd + dia(rc).rd, dia(lc).r, dia(rc).r, dia(lc).rd, dia(rc).rd});
}
void build(int x, int l, int r){
l(x) = l; r(x) = r; tag(x) = 0;
if(l == r){
int p = t1.ret[l]; int td = t1.getdis(1, p);
dia(x) = (node){td, p, p, td, td};
return;
}
int mid = (l + r) >> 1;
build(lc, l, mid); build(rc, mid + 1, r);
pushup(x);
}
il void pushadd(int x, int val){
tag(x) += val;
if(l(x) != r(x)) dia(x).sum += 2ll * val;
else dia(x).sum += val;
dia(x).ld += val; dia(x).rd += val;
}
il void pushdown(int x){
if(tag(x)){
pushadd(lc, tag(x)); pushadd(rc, tag(x)); tag(x) = 0;
}
}
void modify(int x, int l, int r, int val){
if(l <= l(x) && r(x) <= r){pushadd(x, val); return;}
int mid = (l(x) + r(x)) >> 1; pushdown(x);
if(l <= mid) modify(lc, l, r, val);
if(r > mid) modify(rc, l, r, val);
pushup(x);
}
};
using namespace sgtree;
void downcalc(int u, int fa){
for(auto tmp: vq[u]){
int p = tmp.px, id = tmp.py;
int d1 = dia(1).ld + t2.getdis(p, dia(1).l);
int d2 = dia(1).rd + t2.getdis(p, dia(1).r);
ans[id] = max(d1, d2);
}
for(int v, w, i = t1.head[u]; ~ i; i = t1.edge[i].next){
v = t1.edge[i].to; w = t1.edge[i].w; if(v == fa) continue;
if(t1.dfn[v] - 1 >= 1) modify(1, 1, t1.dfn[v] - 1, w);
if(t1.dfn[v] + t1.sz[v] <= n) modify(1, t1.dfn[v] + t1.sz[v], n, w);
modify(1, t1.dfn[v], t1.dfn[v] + t1.sz[v] - 1, -w);
downcalc(v, u);
if(t1.dfn[v] - 1 >= 1) modify(1, 1, t1.dfn[v] - 1, -w);
if(t1.dfn[v] + t1.sz[v] <= n) modify(1, t1.dfn[v] + t1.sz[v], n, -w);
modify(1, t1.dfn[v], t1.dfn[v] + t1.sz[v] - 1, w);
}
}
void work(){
scanf("%lld", &n); t1.init(); t2.init();
scanf("%lld", &q); for(int i = 1; i <= n; i ++) vq[i].clear();
for(int i = 1; i <= q; i ++){int x, y; scanf("%lld %lld", &x, &y); ans[i] = 0; vq[x].pb({y, i});}
build(1, 1, n); downcalc(1, 0);
for(int i = 1; i <= q; i ++) printf("%lld\n", ans[i]);
return;
}
signed main(){
// freopen("move.in", "r", stdin);
// freopen("move.out", "w", stdout);
lg[0] = -1; for(int i = 1; i < N * 2; i ++) lg[i] = lg[i >> 1] + 1;
// int t; scanf("%lld", &t);
int t = 1;
while(t --) work(); return 0;
}
/*
1
3
1 2 1
2 3 2
1 2 2
2 3 1
4
1 1
1 2
2 1
2 2
6
4
5
3
*/
详细
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