[LOJ#2553][CTSC2018]暴力写挂
[LOJ#2553][CTSC2018]暴力寫掛
試題描述
temporaryDO 是一個(gè)很菜的 OIer 。在 4 月，他在省隊(duì)選拔賽的考場(chǎng)上見到了《林克卡特樹》一題，其中 \(k = 0\) 的部分分是求樹 \(T\) 上的最長鏈。可憐的 temporaryDO 并不會(huì)做這道題，他在考場(chǎng)上抓貓耳撓貓腮都想不出一點(diǎn)思路。
這時(shí)，善良的板板出現(xiàn)在了空中，他的身上發(fā)出璀璨卻柔和的光芒，蕩漾在考場(chǎng)上。‘‘題目并不難。’’ 板板說。那充滿磁性的聲音，讓 temporaryDO 全身充滿了力量。 他決定：寫一個(gè)枚舉點(diǎn)對(duì)求 LCA 算距離的 \(k = 0\) 的 $$O(n^2\log\ n)$ 的部分分程序！于是， temporaryDO 選擇以 \(1\) 為根，建立了求 LCA 的樹鏈剖分結(jié)構(gòu)，然后寫了二重 for 循環(huán)枚舉點(diǎn)對(duì)。
然而，菜菜的 temporaryDO 不小心開小了數(shù)組，于是數(shù)組越界到了一片神秘的內(nèi)存區(qū)域。但恰好的是，那片內(nèi)存區(qū)域存儲(chǔ)的區(qū)域恰好是另一棵樹 \(T'\)。這樣一來，程序并沒有 RE ，但他求 \(x\) 和 \(y\) 的距離的時(shí)候，計(jì)算的是
\]
最后程序會(huì)輸出每一對(duì)點(diǎn)對(duì) \(i, j (i \le j)\) 的如上定義的‘‘距離’’ 的最大值。
temporaryDO 的程序在評(píng)測(cè)時(shí)光榮地爆零了。但他并不服氣，他決定花好幾天把自己的程序跑出來。請(qǐng)你根據(jù) \(T\) 和 \(T'\) 幫幫可憐的 temporaryDO 求出他程序的輸出。
輸入
第一行包含一個(gè)整數(shù) \(n\) ，表示樹上的節(jié)點(diǎn)個(gè)數(shù)；
第 \(2\) 到第 \(n\) 行，每行三個(gè)整數(shù) \(x , y , v\)，表示 \(T\) 中存在一條從 \(x\) 到 \(y\) 的邊，其長度為 \(v\)； 第 \(n + 1\) 到第 \(2n - 1\) 行，每行三個(gè)整數(shù) \(x , y , v\)，表示 \(T'\) 中存在一條從 \(x\) 到 \(y\) 的邊，其長度為 \(v\)。
輸出
輸出一行一個(gè)整數(shù)，表示 temporaryDO 的程序的輸出。
輸入示例
6
1 2 2
1 3 0
2 4 1
2 5 -7
3 6 0
1 2 -1
2 3 -1
2 5 3
2 6 -2
3 4 8
輸出示例
5
數(shù)據(jù)規(guī)模及約定
對(duì)于所有數(shù)據(jù)， \(n \le 366666 , |v| \le 2017011328\)。
\(depth(p)\) 和 \(depth'(p)\) 分別表示樹 \(T\)、\(T'\) 中點(diǎn) \(1\) 到點(diǎn) \(p\) 的距離，這里規(guī)定，距離指的是經(jīng)過的邊的邊權(quán)總和，其中 \(depth(1) = 0\)。
\(LCA(x, y)\) 和 \(LCA'(x, y)\) 分別表示樹 \(T\)、\(T'\) 中點(diǎn) \(x\) 與點(diǎn) \(y\) 的最近公共祖先，即在從 \(x\) 到 \(y\) 的最短路徑上的距離根經(jīng)過邊數(shù)最少的點(diǎn)。
題解
擱置已久的大鍋終于搞掉了……這個(gè)題讓自帶大常數(shù)的我卡得生活不能自理……
將第一棵樹轉(zhuǎn)化成二叉樹后邊分治，那么考慮重心邊的兩側(cè)一定有一側(cè)是更“靠近”根的；假設(shè)集合 \(A\) 離根更近，集合 \(B\) 離根更遠(yuǎn)，那么 \(\forall x \in A\) 都有 \(\forall y \in B, y' \in B, lca(x, y) = lca(x, y')\)，其中 \(lca(a, b)\) 表示在原樹上 \(a\) 和 \(b\) 的最近公共祖先。
那么這樣我們可以枚舉 \(x\)，然后 \(depth(x) - depth(lca(x, y))\) 就固定了，我們就是要找到最小的 \(depth(y) - depth'(lca'(x, y))\)，這個(gè)東西建一下虛樹然后樹形 dp 即可（正反兩次 dp，一次從子樹往上推，第二次從父節(jié)點(diǎn)更新到子節(jié)點(diǎn)）。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, t) for(int i = (s), mi = (t); i <= mi; i++)
#define dwn(i, s, t) for(int i = (s), mi = (t); i >= mi; i--)
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
}
#define maxn 800010
#define maxm 1600010
#define maxlog 21
#define pii pair <int, int>
#define x first
#define y second
#define mp(x, y) make_pair(x, y)
#define LL long long
int Log[maxn<<1];
struct tree {
int n, m, head[maxn], nxt[maxm], to[maxm], dist[maxm];
tree(): m(0) { memset(head, 0, sizeof(head)); }
void AddEdge(int a, int b, int c) {
to[++m] = b; dist[m] = c; nxt[m] = head[a]; head[a] = m;
swap(a, b);
to[++m] = b; dist[m] = c; nxt[m] = head[a]; head[a] = m;
return ;
}
} Tmp;
struct Tree {
int n, m, head[maxn], nxt[maxm], to[maxm], dist[maxm], id[maxm], dep[maxn], dfn[maxn], clo, mnp[maxlog][maxn<<1];
LL Dep[maxn];
Tree(): m(0) { memset(head, 0, sizeof(head)); }
void AddEdge(int a, int b, int c, int Id = 0) {
to[++m] = b; dist[m] = c; id[m] = Id; nxt[m] = head[a]; head[a] = m;
swap(a, b);
to[++m] = b; dist[m] = c; id[m] = Id; nxt[m] = head[a]; head[a] = m;
return ;
}
void build(int u, int fa) {
mnp[0][dfn[u] = ++clo] = u;
for(int e = head[u]; e; e = nxt[e]) if(to[e] != fa) {
dep[to[e]] = dep[u] + 1;
Dep[to[e]] = Dep[u] + dist[e];
build(to[e], u);
mnp[0][++clo] = u;
}
return ;
}
void rmq_init() {
Log[1] = 0;
rep(i, 2, clo) Log[i] = Log[i>>1] + 1;
rep(i, 1, Log[clo])
rep(j, 1, clo - (1 << i) + 1) {
int a = mnp[i-1][j], b = mnp[i-1][j+(1<<i>>1)];
mnp[i][j] = dep[a] < dep[b] ? a : b;
}
return ;
}
int lca(int a, int b) {
int l = dfn[a], r = dfn[b];
if(l > r) swap(l, r);
int t = Log[r-l+1], A = mnp[t][l], B = mnp[t][r-(1<<t)+1];
return dep[A] < dep[B] ? A : B;
}
} T, T1;
namespace rebuildTree {
int sons[maxn], sonv[maxn], cs, M;
void getT(int u, int fa) {
for(int e = Tmp.head[u]; e; e = Tmp.nxt[e]) if(Tmp.to[e] != fa) getT(Tmp.to[e], u);
cs = 0;
for(int e = Tmp.head[u]; e; e = Tmp.nxt[e]) if(Tmp.to[e] != fa) sons[++cs] = Tmp.to[e], sonv[cs] = Tmp.dist[e];
// printf("%d has %d sons\n", u, cs);
if(cs <= 2) rep(i, 1, cs) T.AddEdge(u, sons[i], sonv[i], ++M);
else {
T.n++; T.AddEdge(T.n, sons[1], sonv[1], ++M); T.AddEdge(T.n, sons[2], sonv[2], ++M);
rep(i, 3, cs - 1) T.n++, T.AddEdge(T.n, T.n - 1, 0, ++M), T.AddEdge(T.n, sons[i], sonv[i], ++M);
T.AddEdge(u, T.n, 0, ++M); T.AddEdge(u, sons[cs], sonv[cs], ++M);
}
return ;
}
void build() {
getT(1, 0);
// printf("M: %d, %d\n", M, T.n);
T.build(1, 0); T1.build(1, 0);
T.rmq_init(); T1.rmq_init();
return ;
}
}
namespace Solve {
const LL ool = 1ll << 60;
LL ans = -ool;
namespace Vtree {
int KeyPoint[maxn], K;
int m, head[maxn], nxt[maxm], to[maxm];
LL val[maxn], extra[maxn];
void clear() {
rep(i, 1, K) val[KeyPoint[i]] = extra[KeyPoint[i]] = -ool, head[KeyPoint[i]] = 0;
K = m = 0;
return ;
}
void AddEdge(int a, int b) {
to[++m] = b; nxt[m] = head[a]; head[a] = m;
return ;
}
LL f[maxn], pre[maxn], suf[maxn], sonv[maxn];
int son[maxn], cs;
void dp(int u, int fa) {
f[u] = val[u];
for(int e = head[u]; e; e = nxt[e]) dp(to[e], u), f[u] = max(f[u], f[to[e]]);
cs = 0;
for(int e = head[u]; e; e = nxt[e]) son[++cs] = to[e], sonv[cs] = f[to[e]];
LL nmx = -ool;
rep(i, 1, cs) {
pre[son[i]] = nmx;
nmx = max(nmx, sonv[i]);
}
nmx = -ool;
dwn(i, cs, 1) {
suf[son[i]] = nmx;
nmx = max(nmx, sonv[i]);
}
return ;
}
void dp2(int u, int fa, LL nmx) {
if(extra[u] > -ool && (f[u] > -ool || nmx > -ool)) ans = max(ans, extra[u] + max(f[u] - T1.Dep[u], nmx));
for(int e = head[u]; e; e = nxt[e]) {
LL now = max(max(pre[to[e]], suf[to[e]]), val[u]);
dp2(to[e], u, max(nmx, now > -ool ? now - T1.Dep[u] : -ool));
}
return ;
}
bool cmp(const int &a, const int &b) { return T1.dfn[a] < T1.dfn[b]; }
void build() {
sort(KeyPoint + 1, KeyPoint + K + 1, cmp);
rep(i, 1, K - 1) KeyPoint[++K] = T1.lca(KeyPoint[i], KeyPoint[i+1]);
KeyPoint[++K] = T1.lca(KeyPoint[K], KeyPoint[1]);
sort(KeyPoint + 1, KeyPoint + K + 1, cmp);
K = unique(KeyPoint + 1, KeyPoint + K + 1) - KeyPoint - 1;
rep(i, 1, K - 1) {
int a = KeyPoint[i], b = KeyPoint[i+1], c = T1.lca(a, b);
AddEdge(c, b);
}
dp(KeyPoint[1], 0); dp2(KeyPoint[1], 0, -ool);
return ;
}
}
using Vtree::KeyPoint;
using Vtree::K;
using Vtree::val;
using Vtree::extra;
pii rt;
int eid, size, best, siz[maxn];
bool vis[maxn];
void getrt(int u, int fa, int fae) {
siz[u] = 1;
for(int e = T.head[u]; e; e = T.nxt[e]) if(T.id[e] != fae && !vis[T.id[e]]) {
int v = T.to[e];
getrt(v, u, T.id[e]);
siz[u] += siz[v];
}
if(fa && best > max(siz[u], size - siz[u])) best = max(siz[u], size - siz[u]), rt = mp(u, fa), eid = fae;
return ;
}
void dfs(int u, int fae, bool tp) {
if(u <= T1.n) {
KeyPoint[++K] = u;
if(tp) val[u] = T.Dep[u];
else extra[u] = T.Dep[u] - T.Dep[T.lca(u,rt.x)];
}
for(int e = T.head[u]; e; e = T.nxt[e]) if(T.id[e] != fae && !vis[T.id[e]]) dfs(T.to[e], T.id[e], tp);
return ;
}
void solve(pii u, int ed) {
// printf("%d(%d) -- %d(%d)\n", u.x, siz[u.x], u.y, siz[u.y]);
vis[ed] = 1;
if(T.dep[u.x] > T.dep[u.y]) swap(u.x, u.y);
dfs(u.x, 0, 0); dfs(u.y, 0, 1);
Vtree::build();
Vtree::clear();
if(siz[u.x] > 1) {
rt = mp(0, 0); eid = 0; best = (size = siz[u.x]) + 1; getrt(u.x, 0, 0);
if(eid) solve(rt, eid);
}
if(siz[u.y] > 1) {
rt = mp(0, 0); eid = 0; best = (size = siz[u.y]) + 1; getrt(u.y, 0, 0);
if(eid) solve(rt, eid);
}
return ;
}
void main() {
rep(i, 1, T1.n) val[i] = extra[i] = -ool;
rt = mp(0, 0); eid = 0; best = (size = T.n) + 1; getrt(1, 0, 0);
solve(rt, eid);
rep(i, 1, T1.n) ans = max(ans, T.Dep[i] - T1.Dep[i]);
return ;
}
}
int main() {
Tmp.n = T.n = T1.n = read();
rep(i, 1, Tmp.n - 1) {
int a = read(), b = read(), c = read();
Tmp.AddEdge(a, b, c);
}
rep(i, 1, T1.n - 1) {
int a = read(), b = read(), c = read();
T1.AddEdge(a, b, c);
} // */
rebuildTree::build();
Solve::main();
printf("%lld\n", Solve::ans);
return 0;
}
總結(jié)
以上是生活随笔為你收集整理的[LOJ#2553][CTSC2018]暴力写挂的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 关于CORS跨域更细节的思考
- 下一篇： 自动化项目配置或用例文件格式推荐--ya