首页 > 代码库 > SPOJ1825 FTOUR2 - Free tour II
SPOJ1825 FTOUR2 - Free tour II
本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
Description
After the success of 2nd anniversary (take a look at problem FTOUR for more details), this 3rd year, Travel Agent SPOJ goes on with another discount tour.
The tour will be held on ICPC island, a miraculous one on the Pacific Ocean. We list N places (indexed from 1 to N) where the visitors can have a trip. Each road connecting them has an interest value, and this value can be negative(if there is nothing interesting to view there). Simply, these N places along with the roads connecting them form atree structure. We will choose two places as the departure and destination of the tour.
Since September is the festival season of local inhabitants, some places are extremely crowded (we call themcrowded places). Therefore, the organizer of the excursion hopes the tour will visit at most K crowded places (too tiring to visit many of them) and of course, the total number of interesting value should be maximum.
Briefly, you are given a map of N places, an integer K, and M id numbers of crowded place. Please help us to find the optimal tour. Note that we can visit each place only once (or our customers easily feel bored), also the departure and destination places don‘t need to be different.
Input
There is exactly one case. First one line, containing 3 integers N K M, with 1 <= N <= 200000, 0 <= K <= M, 0 <= M <=N.
Next M lines, each line includes an id number of a crowded place.
The last (N - 1) lines describe (N - 1) two-way roads connected N places, form a b i, with a, b is the id of 2 places, and i is its interest value (-10000 <= i <= 10000).
Output
Only one number, the maximum total interest value we can obtain.
Example
Input:
8 2 3
3
5
7
1 3 1
2 3 10
3 4 -2
4 5 -1
5 7 6
5 6 5
4 8 3
Output:
12
Explanation
We choose 2 and 6 as the departure and destination place, so the tour will be 2 -> 3 -> 4 -> 5 -> 6, total interest value = http://www.mamicode.com/10 + (-2) + (-1) + 5 = 12
* Added some unofficial cases
正解：树的点分治
解题报告：
这道题需要统计树上经过黑点数量<=k的路径最长长度。
这种树上的一类路经统计，很快能想到用树分治来做。
考虑当$u$作为根时，我们仅统计经过$u$的所有路径，其余的递归处理。设$G[i]$表示之前的所有子树中经过黑点数量$<=i$的路径最长长度，$dep[i]$表示子节点$i$到其子树中经过的最大黑点数量。
那么，我们可以枚举这次$dfs$的子节点，经过了多少个黑点$j$，那么可以与之组合的就是$G[k-black[u]-j]$，如果$<0$则跳过。
容易发现我们每次统计完一棵子树之后，需要重新更新G，而G[i-1]又需要用G[i]更新，所以统计完这棵子树时，更新$G$和统计答案的复杂度是之前处理的所有节点的$max(dep[i])$，最坏情况可以变成每次都是$n^2$。
考虑统计顺序不影响最终结果，那么我们可以按$dep[i]$排序，从小到大处理，则所有子树的$dep$之和显然$<=n$。
总复杂度$O(nlog^2 n)$
ps：我还是不是很懂为什么这组数据答案是0：
1 0 1
1
这组数据应该没有合法的路径吧...开始一直WA，我调了好久结果特判掉这个点就过了...
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
using namespace std;
typedef long long LL;
const int MAXN = 200011;
const int MAXM = 400011;
const int inf = (1<<30)-1;
int n,k,m,ecnt,first[MAXN],next[MAXM],to[MAXM],w[MAXM],black[MAXN];
bool use[MAXN];
int ans,tot,size[MAXN],S,nowL,nowg[MAXN];
int ansL,G[MAXN],maxd,dep[MAXN];//dep[x]表示x到子树内的所有节点中路径上黑点最多的数量
struct Tree{ int dep,x,z; }b[MAXN];
inline bool cmp(Tree q,Tree qq){ return q.dep<qq.dep; }
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
}
inline void dfs(int x,int fa){
size[x]=1; tot++;
for(int i=first[x];i;i=next[i]) {
int v=to[i]; if(v==fa || use[v]) continue;
dfs(v,x); size[x]+=size[v];
}
}
inline void dfs2(int u,int fa,int &rt){
int maxl=0;
for(int i=first[u];i;i=next[i]) {
int v=to[i]; if(v==fa || use[v]/*!!!*/) continue;
dfs2(v,u,rt); maxl=max(maxl,size[v]);
}
if(tot-size[u]>maxl) maxl=tot-size[u];
if(rt==-1) S=maxl,rt=u;
else if(maxl<S) { S=maxl; rt=u; }
}
inline void find_root(int u,int &rt){
tot=0; dfs(u,0); S=0;
dfs2(u/*!!!*/,0,rt); if(tot==1) rt=-1;
}
inline void getdep(int x,int fa,int dd){
if(black[x]) dd++; if(dd>maxd) maxd=dd;
for(int i=first[x];i;i=next[i]) {
int v=to[i]; if(v==fa || use[v]/*!!!*/) continue;
getdep(v,x,dd);
}
}
inline void dfs3(int x,int fa,int dep,int dd){
if(black[x]) dep++;
if(dep>nowL) { nowL=dep; nowg[dep]=dd; }
else nowg[dep]=max(nowg[dep],dd);
for(int i=first[x];i;i=next[i]) {
int v=to[i]; if(v==fa || use[v]/*!!!*/) continue;
dfs3(v,x,dep,dd+w[i]);
}
}
inline void solve(int u){
int rt=-1; find_root(u,rt);
if(rt==-1) return ; int cnt=0;
u=rt; int now;
for(int i=first[u];i;i=next[i]) {
int v=to[i]; if(use[v]) continue;
maxd=0; getdep(v,u,0); dep[v]=maxd;
b[++cnt].x=v; b[cnt].dep=dep[v]; b[cnt].z=w[i];
}
sort(b+1,b+cnt+1,cmp); ansL=-1;
for(int o=1;o<=cnt;o++) {
int v=b[o].x; nowL=-1;
nowg[0]=-inf;//!!!
dfs3(v,u,0,b[o].z);
for(int i=1;i<=dep[v];i++) nowg[i]=max(nowg[i-1],nowg[i]);
if(ansL>=0) {//查询之前的最优值
for(int i=0;i<=dep[v];i++) {
if(nowg[i]==-inf) continue;
now=k-black[u]-i; if(now<0) break;
if(now>ansL) now=ansL;//!!!
ans=max(ans,G[now]+nowg[i]);
}
}
for(int i=0;i<=ansL;i++) G[i]=max(G[i],nowg[i]);
for(int i=nowL;i>ansL;i--) G[i]=nowg[i];
ansL=nowL;
for(int i=1;i<=ansL;i++) G[i]=max(G[i],G[i-1]);
}
for(int i=0;i<=ansL;i++) if(i+black[u]<=k) ans=max(ans,G[i]); else break;
use[u]=1;
for(int i=first[u];i;i=next[i]) {//!!!
int v=to[i]; if(use[v]) continue;
solve(v);
}
}
inline void work(){
n=getint(); k=getint(); m=getint(); int x,y,z;
for(int i=1;i<=m;i++) { x=getint(); black[x]=1; }
for(int i=1;i<n;i++) {
x=getint(); y=getint(); z=getint();
next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y; w[ecnt]=z;
next[++ecnt]=first[y]; first[y]=ecnt; to[ecnt]=x; w[ecnt]=z;
}
ans=-inf; for(int i=0;i<=n;i++) G[i]=-inf;
solve(1);
if(ans==-inf) {
ans=0;
/*for(int i=1;i<=n;i++)
if(black[i]<=k) { ans=0; break; }*/
}
printf("%d",ans);
}
int main()
{
work();
return 0;
}
SPOJ1825 FTOUR2 - Free tour II