题意：给你三棵树，求所有点对在三棵树上的距离和中的最大值。
解：首先有个暴力，然后还有个迭代乱搞，可以得到61分...
namespace bf {
inline void solve() {
for(int i = ; i <= n; i++) {
for(int j = i; j <= n; j++) {
Ans = std::max(Ans, t1.dis(i, j) + t2.dis(i, j) + t3.dis(i, j));
}
}
printf("%lld\n", Ans);
return;
}
}
namespace naive {
inline void Rand() {
int x = rand() % n + ;
for(int T = ; T <= ; T++) {
int y = ;
LL large = -INF;
for(int i = ; i <= n; i++) {
LL temp = t1.dis(x, i) + t2.dis(x, i) + t3.dis(x, i);
if(temp > large) {
large = temp;
y = i;
}
}
x = y;
Ans = std::max(Ans, large);
}
return;
}
inline void solve() {
for(int i = ; i <= ; i++) {
Rand();
}
printf("%lld\n", Ans);
return;
}
}61分代码
有个部分分是只有两棵树。
我们在第一棵树上枚举lca，那么就相当于把这些点全部挂到第二棵树上，边权是深度。此时可以用直径的性质来维护最远点对。
#define forson(t, x, i) for(int i = t.e[x], y = t.edge[i].v; i; i = t.edge[i].nex, y = t.edge[i].v)
inline bool check_same() {
std::vector<uLL> v, u;
for(int x = ; x <= n; x++) {
v.clear(), u.clear();
forson(t2, x, i) {
v.push_back(t2.edge[i].len * N + y);
}
forson(t3, x, i) {
u.push_back(t3.edge[i].len * N + y);
}
int len = v.size();
if(len != u.size()) return false;
std::sort(v.begin(), v.end());
std::sort(u.begin(), u.end());
for(int i = ; i < len; i++) {
if(v[i] != u[i]) return false;
}
}
return true;
}
namespace same {
Data data[N];
inline LL exdis(const int &x, const int &y) {
return * t2.dis(x, y) + t1.d[x] + t1.d[y];
}
inline void merge(Data &x, const Data &y, const LL &v) {
int xa = x.a, xb = x.b, ya = y.a, yb = y.b;
LL d12 = exdis(xa, xb), d34 = exdis(ya, yb);
LL d13 = exdis(xa, ya), d14 = exdis(xa, yb);
LL d23 = exdis(xb, ya), d24 = exdis(xb, yb);
if(d34 > d12) {
d12 = d34;
x = y;
}
if(d13 > d12) {
d12 = d13;
x.a = xa;
x.b = ya;
}
if(d14 > d12) {
d12 = d14;
x.a = xa;
x.b = yb;
}
if(d23 > d12) {
d12 = d23;
x.a = xb;
x.b = ya;
}
if(d24 > d12) {
d12 = d24;
x.a = xb;
x.b = yb;
}
Ans = std::max(Ans, std::max(std::max(d13, d14), std::max(d23, d24)) - v);
return;
}
void DFS(int x, int f) {
data[x] = Data(x, x);
forson(t1, x, i) {
if(y == f) continue;
DFS(y, x);
merge(data[x], data[y], t1.d[x] << );
}
return;
}
inline void solve() {
DFS(, );
return;
}
}46分代码
正解：这不还有一棵树吗？根据暴力写挂和情报中心的经验，我们边分治 + 虚树，即可去掉第一棵树的限制。把边分治的两部分染成不同颜色。
在第二棵树上建虚树，第三棵树上维护两种颜色的直径。
答案就用不同颜色不同集合的来更新。合并的时候每种颜色分开合并。
/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/ #include <bits/stdc++.h> typedef long long LL;
typedef unsigned long long uLL;
const int N = ;
const LL INF = 4e18; struct Edge {
int nex, v;
LL len;
bool vis;
}edge[N << ], EDGE[N << ]; int tp = , TP; struct Data {
int a, b;
LL v;
Data(int A = , int B = , LL V = ) {
a = A;
b = B;
v = V;
}
}data1[N], data2[N]; int pw[N << ], n, rdP[N], e[N], siz[N], Cnt, _n, small, root, use[N], Time, vis[N], E[N], K, imp[N], RT, col[N];
LL Ans, d[N]; struct Tree {
Edge edge[N << ]; int tp = ;
int e[N], pos2[N], num2, ST[N << ][], deep[N];
LL d[N];
inline void add(int x, int y, LL z) {
edge[++tp].v = y;
edge[tp].len = z;
edge[tp].nex = e[x];
e[x] = tp;
return;
}
void DFS_1(int x, int f) {
pos2[x] = ++num2;
ST[num2][] = x;
deep[x] = deep[f] + ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == f) continue;
d[y] = d[x] + edge[i].len;
DFS_1(y, x);
ST[++num2][] = x;
}
return;
}
inline void prework() {
for(int j = ; j <= pw[num2]; j++) {
for(int i = ; i + ( << j) - <= num2; i++) {
if(deep[ST[i][j - ]] < deep[ST[i + ( << (j - ))][j - ]]) {
ST[i][j] = ST[i][j - ];
}
else {
ST[i][j] = ST[i + ( << (j - ))][j - ];
}
}
}
return;
}
inline int lca(int x, int y) {
x = pos2[x];
y = pos2[y];
if(x > y) std::swap(x, y);
int t = pw[y - x + ];
if(deep[ST[x][t]] < deep[ST[y - ( << t) + ][t]]) {
return ST[x][t];
}
else {
return ST[y - ( << t) + ][t];
}
}
inline LL dis(int x, int y) {
if(!x || !y) {
return -INF;
}
return d[x] + d[y] - (d[lca(x, y)] << );
}
inline void work() {
LL z;
for(int i = , x, y; i < n; i++) {
scanf("%d%d%lld", &x, &y, &z);
add(x, y, z);
add(y, x, z);
}
DFS_1(, );
prework();
return;
}
#undef add
}t1, t2, t3; namespace bf {
inline void solve() {
for(int i = ; i <= n; i++) {
for(int j = i; j <= n; j++) {
Ans = std::max(Ans, t1.dis(i, j) + t2.dis(i, j) + t3.dis(i, j));
}
}
return;
}
} namespace naive {
inline void Rand() {
int x = rand() % n + ;
for(int T = ; T <= ; T++) {
int y = ;
LL large = -INF;
for(int a = ; a <= n; a++) {
int i = rdP[a];
LL temp = t1.dis(x, i) + t2.dis(x, i) + t3.dis(x, i);
if(temp > large) {
large = temp;
y = i;
}
}
x = y;
Ans = std::max(Ans, large);
}
return;
}
inline void solve() {
for(int i = ; i <= ; i++) {
Rand();
}
return;
}
} namespace fire {
inline void Rand() {
int x = rand() % n + ;
for(int T = ; T <= ; T++) {
int y = ;
LL large = -INF;
for(int a = ; a <= n; a++) {
int i = rdP[a];
LL temp = t1.dis(x, i) + t2.dis(x, i) + t3.dis(x, i);
if(temp > large) {
large = temp;
y = i;
}
else if(rand() % < T) {
large = temp;
y = i;
}
}
x = y;
Ans = std::max(Ans, large);
}
return;
}
inline void solve() {
for(int i = ; i <= ; i++) {
Rand();
}
return;
}
} #define forson(t, x, i) for(int i = t.e[x], y = t.edge[i].v; i; i = t.edge[i].nex, y = t.edge[i].v) inline bool check_same() {
std::vector<uLL> v, u;
for(int x = ; x <= n; x++) {
v.clear(), u.clear();
forson(t2, x, i) {
v.push_back(t2.edge[i].len * N + y);
}
forson(t3, x, i) {
u.push_back(t3.edge[i].len * N + y);
}
int len = v.size();
if(len != u.size()) return false;
std::sort(v.begin(), v.end());
std::sort(u.begin(), u.end());
for(int i = ; i < len; i++) {
if(v[i] != u[i]) return false;
}
}
return true;
} namespace same {
Data data[N];
inline LL exdis(const int &x, const int &y) {
return * t2.dis(x, y) + t1.d[x] + t1.d[y];
}
inline void merge(Data &x, const Data &y, const LL &v) {
int xa = x.a, xb = x.b, ya = y.a, yb = y.b;
LL d12 = exdis(xa, xb), d34 = exdis(ya, yb);
LL d13 = exdis(xa, ya), d14 = exdis(xa, yb);
LL d23 = exdis(xb, ya), d24 = exdis(xb, yb);
if(d34 > d12) {
d12 = d34;
x = y;
}
if(d13 > d12) {
d12 = d13;
x.a = xa;
x.b = ya;
}
if(d14 > d12) {
d12 = d14;
x.a = xa;
x.b = yb;
}
if(d23 > d12) {
d12 = d23;
x.a = xb;
x.b = ya;
}
if(d24 > d12) {
d12 = d24;
x.a = xb;
x.b = yb;
}
Ans = std::max(Ans, std::max(std::max(d13, d14), std::max(d23, d24)) - v);
return;
}
void DFS(int x, int f) {
data[x] = Data(x, x);
forson(t1, x, i) {
if(y == f) continue;
DFS(y, x);
merge(data[x], data[y], t1.d[x] << );
}
return;
}
inline void solve() {
DFS(, );
return;
}
} #undef forson inline void add(int x, int y, LL z) {
edge[++tp].v = y;
edge[tp].len = z;
edge[tp].nex = e[x];
e[x] = tp;
return;
} inline void ADD(int x, int y) {
EDGE[++TP].v = y;
EDGE[TP].nex = E[x];
E[x] = TP;
return;
} void rebuild(int x, int f) {
int temp = ;
for(int i = t1.e[x]; i; i = t1.edge[i].nex) {
int y = t1.edge[i].v;
LL len = t1.edge[i].len;
if(y == f) continue;
if(!temp) {
add(x, y, len);
add(y, x, len);
temp = x;
}
else if(!t1.edge[i].nex) {
add(temp, y, len);
add(y, temp, len);
}
else {
add(temp, ++Cnt, );
add(Cnt, temp, );
temp = Cnt;
add(temp, y, len);
add(y, temp, len);
}
rebuild(y, x);
}
return;
} void getroot(int x, int f) {
siz[x] = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == f || edge[i].vis) continue;
getroot(y, x);
siz[x] += siz[y];
if(std::max(siz[y], _n - siz[y]) < small) {
small = std::max(siz[y], _n - siz[y]);
root = i;
}
}
return;
} inline void work(int x) {
if(use[x] == Time) return;
use[x] = Time;
E[x] = col[x] = ;
return;
} void DFS_1(int x, int f, int flag) {
siz[x] = ;
if(x <= n) {
work(x);
imp[++K] = x;
col[x] = flag;
}
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == f || edge[i].vis) continue;
d[y] = d[x] + edge[i].len;
DFS_1(y, x, flag);
siz[x] += siz[y];
}
return;
} inline bool cmp(const int &a, const int &b) {
return t2.pos2[a] < t2.pos2[b];
} inline void build_t() {
static int stk[N], top;
std::sort(imp + , imp + K + , cmp);
K = std::unique(imp + , imp + K + ) - imp - ;
stk[top = ] = imp[];
for(int i = ; i <= K; i++) {
int x = imp[i], y = t2.lca(x, stk[top]);
work(y);
while(top > && t2.pos2[y] <= t2.pos2[stk[top - ]]) {
ADD(stk[top - ], stk[top]);
top--;
}
if(stk[top] != y) {
ADD(y, stk[top]);
stk[top] = y;
}
stk[++top] = x;
}
while(top > ) {
ADD(stk[top - ], stk[top]);
top--;
}
RT = stk[top];
return;
} inline bool operator < (const Data &a, const Data &b) {
return a.v < b.v;
} inline LL exdis(int x, int y) {
return t3.dis(x, y) + d[x] + d[y] + t2.d[x] + t2.d[y];
} inline void merge(Data &x, const Data &y) {
int xa = x.a, xb = x.b, ya = y.a, yb = y.b;
LL d12 = exdis(xa, xb), d34 = exdis(ya, yb);
LL d13 = exdis(xa, ya), d14 = exdis(xa, yb);
LL d23 = exdis(xb, ya), d24 = exdis(xb, yb);
if(d34 > d12) {
d12 = d34;
x = y;
}
if(d13 > d12) {
d12 = d13;
x.a = xa;
x.b = ya;
}
if(d14 > d12) {
d12 = d14;
x.a = xa;
x.b = yb;
}
if(d23 > d12) {
d12 = d23;
x.a = xb;
x.b = ya;
}
if(d24 > d12) {
x.a = xb;
x.b = yb;
}
return;
} inline void merge(int x, int y, LL v) {
int p1 = data1[x].a, p2 = data1[x].b, p3 = data2[x].a, p4 = data2[x].b;
int p5 = data1[y].a, p6 = data1[y].b, p7 = data2[y].a, p8 = data2[y].b;
/// cal ans
Ans = std::max(Ans, std::max(std::max(exdis(p1, p7), exdis(p1, p8)), std::max(exdis(p2, p7), exdis(p2, p8))) + v);
Ans = std::max(Ans, std::max(std::max(exdis(p3, p5), exdis(p3, p6)), std::max(exdis(p4, p5), exdis(p4, p6))) + v);
/// update data1[x] data2[x]
merge(data1[x], data1[y]);
merge(data2[x], data2[y]);
return;
} void DFS_2(int x, LL v) {
data1[x] = data2[x] = Data(, );
if(col[x] == ) {
data1[x] = Data(x, x);
}
else if(col[x] == ) {
data2[x] = Data(x, x);
}
for(int i = E[x]; i; i = EDGE[i].nex) {
int y = EDGE[i].v;
DFS_2(y, v);
merge(x, y, v - (t2.d[x] << ));
}
return;
} void e_div(int x) {
if(_n == ) {
return;
}
small = N;
getroot(x, );
edge[root].vis = edge[root ^ ].vis = ;
x = edge[root].v;
int y = edge[root ^ ].v; ++Time;
d[x] = d[y] = K = TP = ;
DFS_1(x, , );
DFS_1(y, , );
build_t();
DFS_2(RT, edge[root].len); ///
_n = siz[x];
e_div(x);
_n = siz[y];
e_div(y);
return;
} int main() { srand();
scanf("%d", &n);
for(int i = ; i <= * n; i++) {
pw[i] = pw[i >> ] + ;
}
for(int i = ; i <= n; i++) {
rdP[i] = i;
}
std::random_shuffle(rdP + , rdP + n + );
t1.work();
t2.work();
t3.work();
/*if(n <= 3000) {
bf::solve();
printf("%lld\n", Ans);
return 0;
}
if(check_same()) {
same::solve();
printf("%lld\n", Ans);
return 0;
}
naive::solve();
fire::solve();*/
/// ---------------------------
Cnt = n;
rebuild(, );
_n = Cnt;
e_div();
printf("%lld\n", Ans);
return ;
}
AC代码
其实也不是很长......大概只有hope的一半多一点。虽然我没写hope......