Free tour II SPOJ - FTOUR2

点分治

 每次选择重心作为根进行分治，有两种情况，最优解的路径经过树根，和不经过根

不经过根

递归到下一层子树上

经过根

暴力选择两个子树求最优的情况

先考虑暴力的情况
需要选择两个子树u,v
G(i,j) 代表子树i，往下选择j个黑点时的最大权值
dep(i) 代表选择子树i，向下最多有多少个黑点
对每个子树都暴力搜索，O(n) 可以求出G(i,j) 和dep(i)
对于G(i,j) 我们有以下规则
最多有dep(i) 个黑点，那么如果G(i,j) 中j>dep(i) ，则不存在j个黑点，可以看做等于G(i,dep(j));
还有一个规则，那么就是如果选择j个黑点还没有选择j-1个黑点优，那么这个j个黑点的值对答案没有贡献，可以令G(i,j) = G(i,j-1);
这样求出来的G(i,j) 就是单调增的，即G(i,j) >= G(i,j-1)
在第一个子树中选取k1个黑点，在另一个子树中选取k2个点，k1+k2 <= k,求最优值
我们有以下规则，dep(u) > dep(v) 那么我们枚举k1,从0，到dep(u)，这样枚举的复杂度dep(u)+dep(v);
有了上一个的限制，选取两个子树的时候我们肯定是尽量凑够k个黑点使得权值最大，那么就如果求出每个子树
我们知道sum(dep(i)) = m <= n
分析以下总的复杂度，发现枚举u,v的复杂度高达n^2

启发式合并

怎么优化呢，就是我们选则一个子树v 的时候，和前面所有已经求过得子树求最大值，求完最大值，把这个子树也合并进去，我们用一个
mx[j]的数组记录前v-1的子树选择j个黑点时候的最优值，这样就不用暴力枚举u，v了
可是如果我们选择的第一个子树上就有很多个黑点的话，复杂度可能会爆炸，怎么办呢
就是先对所有的子树，按照dep(i)进行排序，小的在前，这样下去的复杂度就会变为dep(1)+dep(2)+…dep(子树的个数) <= n
所以一次计算的复杂度就降为n
由于边的个数是O(N)的，所以在排序这个环节我们的总复杂度不超过O(N log N)

参考代码

typedef pair<int,int> P; const int maxn = 2e5+200; bool black[maxn]; // 前向星存图 struct Edge{ int to,w,next; }edge[maxn<<1]; int tot = 0; int head[maxn]; void init(){ tot = 0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w){ edge[++tot].to = v,edge[tot].w = w,edge[tot].next = head[u],head[u] = tot; } // 求重心 int dp[maxn],size[maxn]; bool vis[maxn]; void getroot(int u,int fa,int allnode,int &root){ size[u] = 1; dp[u] = 0; for(int i = head[u],to;i != -1; i = edge[i].next){ to = edge[i].to; if(vis[to]||to == fa) continue; getroot(to,u,allnode,root); size[u] += size[to]; dp[u] = max(dp[u],size[to]); } dp[u] = max(dp[u],allnode-size[u]); if(dp[u] < dp[root]) root = u; } int ans = 0; int G[maxn],mx[maxn],dep[maxn]; int dis[maxn]; int maxdep; void dfsdepth(int u,int fa){ maxdep = max(maxdep,dep[u]); for(int i = head[u],to;i != -1; i = edge[i].next){ to = edge[i].to; if(vis[to] || to == fa) continue; dep[to] = dep[u] + black[to]; dis[to] = dis[u] + edge[i].w; dfsdepth(to,u); } } void dfsG(int u,int fa){ G[dep[u]] = max(G[dep[u]],dis[u]); for(int i = head[u],to;i != -1; i = edge[i].next){ to = edge[i].to; if(vis[to] || to == fa) continue; dfsG(to,u); } } vector<P> v; void solve(int u,int k){ vis[u] = true; if(black[u]) k--;// 假设选择出来的最优权值经过u点 v.clear(); for(int i = head[u],to;i != -1; i = edge[i].next){ to = edge[i].to; if(vis[to]) continue; maxdep = 0;dep[to] = black[to];dis[to] = edge[i].w; dfsdepth(to,u); //cout<<maxdep<<endl; v.push_back(P(maxdep,to)); } sort(v.begin(),v.end()); for(int i = 0;i < v.size(); ++i){ //cout<<ans<<endl; int to = v[i].SE,all = v[i].FI; dfsG(to,u); if(i){ for(int k1 = 0,k2 = v[i-1].FI;k1 <= all; ++k1){ while(k1+k2 > k&&k2 > 0) k2--; if(k1) G[k1] = max(G[k1],G[k1-1]); if(k1 + k2 <= k) ans = max(ans,G[k1]+mx[k2]); } } if(i+1 ==v.size()){ for(int j = 0;j <= all; ++j) mx[j] = 0,G[j] = 0; } else{ for(int j = 0;j <= all; ++j){ mx[j] = max(mx[j],G[j]),G[j] = 0; if(j) mx[j] = max(mx[j],mx[j-1]); } } } if(black[u]) k++; // 用重心分治 for(int i = head[u],to; i != -1;i = edge[i].next){ to = edge[i].to; if(vis[to]) continue; int root = 0; getroot(to,-1,size[to],root); //cout<<root<<endl; solve(root,k); } } int main(void) { init(); int n,m,k; scanf("%d%d%d",&n,&k,&m); while(m--){ int v; scanf("%d",&v); black[v] = true; } rep(i,1,n){ int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } dp[0] = INF;int root = 0; getroot(1,-1,n,root); //cout<<root<<endl; solve(root,k); printf("%d\n",ans); return 0; }