QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#696171#5439. Meet in the MiddleCode_quantumTL 0ms0kbC++144.9kb2024-10-31 21:43:102024-10-31 21:43:10

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 21:43:10]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [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

output:


result: