题目大意

给出一棵树，边上有权值，要求给出一个1到n的排列p，使得sigma d(i, pi)最大，且p的字典序尽量小。

d(u, v)为树上两点u和v的距离

 

题解：一开始没看出来p需要每个数都不同，直接敲了个轻重边剖分orz，交上去才发现不对

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define fi first#define se secondusing namespace std;typedef long long LL;typedef pair
         
           PII;typedef pair
          
            PLI;const int maxn = 1e5 + 100;PLI dp[maxn], dp2[maxn];vector
           
             G[maxn];int son[maxn];void dfs(int x, int fa){ dp[x].se = x; dp[x].fi = 0; 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 = 1; i < n; i++){ cin>>x>>y>>w; G[x].push_back({y, w}); G[y].push_back({x, w}); } dfs(1, 1); LL ans = 0; vector
            
              V; ans += dp[1].fi; V.push_back(dp[1].se); dp2[1].se = 1; for(auto e : G[1]){ if(e.fi == son[1]) continue; Maintain(e.se, dp[e.fi], dp2[1]); } for(auto e : G[1]) ddfs(e.fi, 1, e.se); for(int i = 2; 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<
             
              <
             
            
           
          
         
        
       
      
     

 

 

题解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 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define fi first#define se secondusing namespace std;const int maxn = 1e5 + 100;typedef long long LL;typedef pair
          
            PLI;typedef pair
           
             PII;vector
            
              G[maxn];set
             
               S;int son[maxn], sz[maxn], f[maxn], col[maxn], ll[maxn], rr[maxn], no[maxn], ans[maxn], M[maxn];int tree[maxn*4];int n, tot;LL ANS = 0;void dfs0(int x, int fa){ sz[x] = 1; 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] = 1; 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)>>1; if(k <= mid) Insert(o*2, l, mid, k, v); else Insert(o*2+1, mid+1, r, k, v); tree[o] = min(tree[o*2], tree[o*2+1]);}int Query(int o, int l, int r, int L, int R){ if(L <= l && r <= R) return tree[o]; int mid = (l+r)>>1, ans = 1e9; if(L <= mid) ans = min(ans, Query(o*2, l, mid, L, R)); if(R > mid) ans = min(ans, Query(o*2+1, mid+1, r, L, R)); return ans;}void dfs1(int x, int fa, int cc){ f[x] = ++tot; col[x] = cc; Insert(1, 1, 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+1 < 0) S.insert({x.fi+1, col});}int main(){ cin>>n; for(int i = 1; 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(1, 1); for(int i = 1; i <= n; i++) if(son[i] <= n/2) X = i; dfs(X, X, 0); cout<
              
               <
               
                 0) y = min(y, Query(1, 1, n, 1, l-1)); if(r+1 <= n) y = min(y, Query(1, 1, n, r+1, n)); if(f[i] == n) y = min(i, y); Insert(1, 1, n, f[y], 1e9); ans[i] = y; Erase(col[i]); no[col[i]]--; Erase(col[y]); M[col[y]]--; } for(int i = 1; i <= n; i++) cout<
                
                 <<" ";}