题目大意
给出一棵树，边上有权值，要求给出一个1到n的排列p，使得sigma d(i, pi)最大，且p的字典序尽量小。
d(u, v)为树上两点u和v的距离
题解：一开始没看出来p需要每个数都不同，直接敲了个轻重边剖分orz，交上去才发现不对
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<long long, int> PLI;
const int maxn = 1e5 + ;
PLI dp[maxn], dp2[maxn];
vector<PII> G[maxn];
int son[maxn]; void dfs(int x, int fa){
dp[x].se = x;
dp[x].fi = ;
for(auto e : G[x]){
if(e.fi == fa) continue;
dfs(e.fi, x);
if(dp[e.fi].fi + e.se >= dp[x].fi){
if(dp[e.fi].fi + e.se == dp[x].fi){
son[x] = dp[x].se < dp[e.fi].se ? son[x] : e.fi;
dp[x].se = min(dp[x].se, dp[e.fi].se);
} else {
son[x] = e.fi;
dp[x].fi = dp[e.fi].fi + e.se;
dp[x].se = dp[e.fi].se;
}
}
}
} void Maintain(LL v, PLI A, PLI& B){
if(v + A.fi > B.fi){
B.fi = v + A.fi;
B.se = A.se;
} else if(v + A.fi == B.fi){
B.se = B.se < A.se ? B.se : A.se;
}
} void ddfs(int x, int fa, LL v){
dp2[x].se = x;
for(auto e : G[x]){
if(e.fi == fa) continue;
if(e.fi == son[x]) continue;
Maintain(e.se, dp[e.fi], dp2[x]);
}
if(son[fa] == x){
Maintain(v, dp2[fa], dp2[x]);
} else {
Maintain(v, dp[fa], dp2[x]);
Maintain(v, dp2[fa], dp2[x]);
}
for(auto e : G[x]) if(e.fi != fa) ddfs(e.fi, x, e.se);
} int main()
{
int n, x, y, w;
cin>>n;
for(int i = ; i < n; i++){
cin>>x>>y>>w;
G[x].push_back({y, w});
G[y].push_back({x, w});
}
dfs(, );
LL ans = ;
vector<int> V;
ans += dp[].fi; V.push_back(dp[].se);
dp2[].se = ;
for(auto e : G[]){
if(e.fi == son[]) continue;
Maintain(e.se, dp[e.fi], dp2[]);
}
for(auto e : G[]) ddfs(e.fi, , e.se);
for(int i = ; i <= n; i++){
if(dp[i].fi > dp2[i].fi){
ans += dp[i].fi;
V.push_back(dp[i].se);
} else if(dp[i].fi == dp2[i].fi){
ans += dp[i].fi;
V.push_back(dp[i].se < dp2[i].se ? dp[i].se : dp2[i].se);
} else {
ans += dp2[i].fi;
V.push_back(dp2[i].se);
}
}
cout<<ans<<endl;
for(auto x : V) cout<<x<<" "; }
题解2：
如果排列要求都不同的话，实际上求最大值反而好求了
考虑在以任意点x为根，u和v匹配的答案
就是dis(x, u) + dis(x, v) - dis(x, lca(u, v))
如果这个点x是树的重心，我们就可以使得每个匹配的lca都是x，这时就可以得到最优解
所以求最优解还是很容易的
接下来是匹配
匹配实际上并不好做，需要考虑下面几个问题
1、找到树的重心以后，需要把每颗子树的dfs序用线段树维护，然后用线段树查询值最小的点
2、在匹配的过程中，有可能出现如果把u和v匹配之后，后面就无法完成匹配的情况，这时只能用u来匹配最需要匹配的那棵子树
这个理解起来可能比较抽象，写成具体的式子实际上是
令px[i]表示子树i内还有多少个点没有跟其他子树中的点匹配
py[i]表示子树i内还有多少个点没有被（强调被动）其他子树中的点匹配
如果当前还有y个点没进行匹配，那么如果存在一颗子树i, y < px[i] + py[i]，实际上就必须要优先考虑i子树了。
因为如果还是按照字典序匹配，就会造成后续的i子树外需要匹配的点的个数，小于i子树内需要被匹配的点的个数，就根本无法完成匹配！
当然如果这个点本身还是在i子树内的话，那么还是可以和其他子树匹配的，（因为y和px[i]同时减1，不影响后续匹配）
3、重心可以和重心本身匹配，这很扯。。但是确实是可行的，需要特殊考虑
实现过程的时候，用set来维护px[i] + py[i]，如果出现了y < px[i] + py[i]，就进行特殊处理。
没出现就按字典序查询匹配。整个过程都要动态维护px[i], py[i]的值
然后线段树维护dfs序不再多说。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#define fi first
#define se second
using namespace std;
const int maxn = 1e5 + ;
typedef long long LL;
typedef pair<long long, int> PLI;
typedef pair<int, int> PII;
vector<PLI> G[maxn];
set<PII> S;
int son[maxn], sz[maxn], f[maxn], col[maxn], ll[maxn], rr[maxn], no[maxn], ans[maxn], M[maxn];
int tree[maxn*];
int n, tot;
LL ANS = ;
void dfs0(int x, int fa){
sz[x] = ;
for(auto e : G[x]){
if(e.fi == fa) continue;
dfs0(e.fi, x);
sz[x] += sz[e.fi];
son[x] = max(son[x], sz[e.fi]);
}
son[x] = max(son[x], n - sz[x]);
} void dfs(int x, int fa, LL v){
sz[x] = ;
for(auto e : G[x]){
if(e.fi == fa) continue;
dfs(e.fi, x, e.se+v);
sz[x] += sz[e.fi];
}
ANS += v;
} void Insert(int o, int l, int r, int k, int v){
if(l == r) { tree[o] = v; return; }
int mid = (l+r)>>;
if(k <= mid) Insert(o*, l, mid, k, v);
else Insert(o*+, mid+, r, k, v);
tree[o] = min(tree[o*], tree[o*+]);
}
int Query(int o, int l, int r, int L, int R){
if(L <= l && r <= R) return tree[o];
int mid = (l+r)>>, ans = 1e9;
if(L <= mid) ans = min(ans, Query(o*, l, mid, L, R));
if(R > mid) ans = min(ans, Query(o*+, mid+, r, L, R));
return ans;
} void dfs1(int x, int fa, int cc){
f[x] = ++tot;
col[x] = cc;
Insert(, , n, tot, x);
for(auto e : G[x]){
if(e.fi == fa) continue;
dfs1(e.fi, x, cc);
}
} void Erase(int col){
PII x = make_pair(-M[col]-no[col], col);
S.erase(x);
if(x.fi+ < ) S.insert({x.fi+, col});
} int main()
{
cin>>n;
for(int i = ; i < n; i++){
int x, y, w;
cin>>x>>y>>w;
G[x].push_back({y, w});
G[y].push_back({x, w});
}
int X;
dfs0(, );
for(int i = ; i <= n; i++) if(son[i] <= n/) X = i;
dfs(X, X, );
cout<<ANS*<<endl;
int flag = , N = ;
for(auto e : G[X]){
ll[++N] = tot+;
dfs1(e.fi, X, N);
rr[N] = tot;
S.insert({-*sz[e.fi], N});
M[N] = no[N] = sz[e.fi];
}
f[X] = ++tot;
Insert(, , n, tot, X);
ll[++N] = tot;
rr[N] = tot;
col[X] = N;
S.insert({, N});
M[N] = no[N] = ;
int l, r;
for(int i = ; i <= n; i++){
auto x = *S.begin();
int rem = n-i+;
if(col[i] != x.se){
rem--;
if(rem < -x.fi){
l = ll[x.se], r = rr[x.se];
int y = Query(, , n, l, r);
ans[i] = y;
Erase(x.se);
M[x.se]--;
Insert(, , n, f[y], 1e9);
Erase(col[i]);
no[col[i]]--;
continue;
}
}
l = ll[col[i]], r = rr[col[i]];
int y = 1e9;
if(l- > ) y = min(y, Query(, , n, , l-));
if(r+ <= n) y = min(y, Query(, , n, r+, n));
if(f[i] == n) y = min(i, y);
Insert(, , n, f[y], 1e9);
ans[i] = y;
Erase(col[i]);
no[col[i]]--;
Erase(col[y]);
M[col[y]]--;
}
for(int i = ; i <= n; i++) cout<<ans[i]<<" ";
}