QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87475#5439. Meet in the MiddleAcestarWA 47ms36800kbC++143.3kb2023-03-13 09:51:502023-03-13 09:51:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-13 09:51:53]
  • 评测
  • 测评结果:WA
  • 用时:47ms
  • 内存:36800kb
  • [2023-03-13 09:51:50]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define ll long long

typedef pair<int, ll> P;
#define fi first
#define se second

const int N = 1e5 + 5;
const int M = 5e5 + 5;

int n, m;
vector <P> q[N];
ll ans[M];

struct Tree
{
	vector <P> G[N];
	int fa[N], siz[N], son[N], dep[N];
	ll dis[N];
	int top[N], tim, dfn[N], id[N];
	
	void dfs1(int u, int p)
	{
		fa[u] = p, siz[u] = 1, dep[u] = dep[p] + 1;
		for(auto v : G[u])
		{
			if(v.fi == p) continue;
			dis[v.fi] = dis[u] + v.se;
			dfs1(v.fi, u); siz[u] += siz[v.fi];
			if(siz[v.fi] > siz[son[u]]) son[u] = v.fi;
		}
		return;
	}
	
	void dfs2(int u, int tp)
	{
		top[u] = tp, dfn[u] = ++tim, id[tim] = u;
		if(son[u]) dfs2(son[u], tp);
		for(auto v : G[u])
			if(v.fi != fa[u] && v.fi != son[u]) dfs2(v.fi, v.fi);
		return;
	}
	
	int LCA(int x, int y)
	{
		while(top[x] != top[y])
		{
			if(dep[top[x]] < dep[top[y]]) swap(x, y);
			x = fa[top[x]];
		}
		return dep[x] < dep[y] ? x : y;
	}
	
	ll Dis(int x, int y)
	{
		if(!x || !y) return 0;
		return dis[x] + dis[y] - dis[LCA(x, y)] * 2;
	}
} A, B;

struct Path
{
	P s, t; ll dis;
	Path(P _s = {0, 0}, P _t = {0, 0}) {s = _s, t = _t, dis = B.Dis(s.fi, t.fi) + s.se + t.se;}
	bool operator < (const Path &rhs) const {return dis < rhs.dis;}
    friend Path operator + (Path x, Path y)
    {
        Path z = max(x, y);
        z = max({z, Path(x.s, y.s), Path(x.s, y.t)});
        z = max({z, Path(x.t, y.s), Path(x.t, y.t)});
        return z;
    }
};

#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid ((l + r) >> 1)

Path t[N << 2];
ll tag[N << 2];

void pushtag(int rt, ll v)
{
    t[rt].s.se += v, t[rt].t.se += v;
    if(t[rt].t.fi) t[rt].dis += 2 * v;
	tag[rt] += v;
}

void pushdown(int rt)
{
	if(!tag[rt]) return;
	pushtag(ls, tag[rt]), pushtag(rs, tag[rt]);
	tag[rt] = 0;
}

void build(int l, int r, int rt)
{
	if(l == r) return t[rt] = Path({A.id[l], A.dis[A.id[l]]}, {0, 0}), void();
	build(l, mid, ls), build(mid + 1, r, rs);
    t[rt] = t[ls] + t[rs];
}

void upd(int L, int R, int v, int l = 1, int r = n, int rt = 1)
{
	if(L > R || l > R || r < L) return;
	if(L <= l && r <= R) return pushtag(rt, v);
	pushdown(rt);
	upd(L, R, v, l, mid, ls), upd(L, R, v, mid + 1, r, rs);
    t[rt] = t[ls] + t[rs];
}

void update(int l, int r, int v)
{
    upd(1, n, v), upd(l, r, -2 * v);
}

ll qry(int x)
{
    Path p = t[1];
    return max(B.Dis(x, p.s.fi) + p.s.se, B.Dis(x, p.t.fi) + p.t.se);
}

void dfs3(int u)
{
	for(auto p : q[u]) ans[p.se] = qry(p.fi);
	for(auto v : A.G[u])
	{
		if(v.fi == A.fa[u]) continue;
		update(A.dfn[v.fi], A.dfn[v.fi] + A.siz[v.fi] - 1, v.se);
		dfs3(v.fi);
		update(A.dfn[v.fi], A.dfn[v.fi] + A.siz[v.fi] + 1, -v.se);
	}
	return;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> n >> m;
	for(int i = 1, u, v, w; i < n; i++)
		cin >> u >> v >> w, A.G[u].push_back({v, w}), A.G[v].push_back({u, w});
	for(int i = 1, u, v, w; i < n; i++)
		cin >> u >> v >> w, B.G[u].push_back({v, w}), B.G[v].push_back({u, w});
	for(int i = 1, a, b; i <= m; i++)
		cin >> a >> b, q[a].push_back({b, i});

	A.dfs1(1, 0), A.dfs2(1, 1);
	B.dfs1(1, 0), B.dfs2(1, 1);
	build(1, n, 1); dfs3(1);

	for(int i = 1; i <= m; i++) cout << ans[i] << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 32728kb

input:

3 4
1 2 1
2 3 2
1 2 2
2 3 1
1 1
1 2
2 1
2 2

output:

6
4
5
3

result:

ok 4 number(s): "6 4 5 3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 34536kb

input:

2 1
1 2 1
1 2 1
1 1

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 0ms
memory: 34548kb

input:

2 1
1 2 1
1 2 1
1 2

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: -100
Wrong Answer
time: 47ms
memory: 36800kb

input:

10000 50000
8101 5996 108427744
5996 7605 870838849
5996 5599 603303696
8101 3006 339377417
8101 6463 442516687
6463 5560 109174079
5560 4063 127596224
3006 1682 947915262
5996 1986 130416311
6463 5455 279771516
6463 2634 516688796
4063 3034 217886863
7605 5092 742375061
5599 2266 193804402
5092 140...

output:

633782135171
616489177187
514273941704
637066393138
462495763607
645842915960
641998753292
573604504956
634030959481
803875451466
674831444020
734764046916
745800835759
764716413834
553960779194
527204718793
611311739832
690011141076
549622196856
726811438160
654072264438
666761991962
701575393972
6...

result:

wrong answer 1st numbers differ - expected: '647838384844', found: '633782135171'