[原创]SPOJ FTOUR2 - Free tour II [点分治+启发式合并]【分治】

2017-07-18 09:10:38 Tabris_ 阅读数：892

博客爬取于2020-06-14 22:39:37
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/75270526

题目链接：http://www.spoj.com/problems/FTOUR2/
—————————————————————————————————————
FTOUR2 - Free tour II
no tags
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 a tree 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 them crowded 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 = 10 + (-2) + (-1) + 5 = 12

  • Added some unofficial cases
    ——————————————————————————————————————

题目大意：
给你一棵树，树上的节点有白点有黑点，其中找到一条路径使得在经过的黑色点数不超过K的时候 路径长度最大，输出这个最大值

最好去看论文===>戳这里

注意! 注意! 这里最小值要初始化为0,而不是-INF,可以路径上只有一个点…wa到死有没有!!!

还是采用点分治,

首先 对于每个子树 找 经过根节点的 满足条件 最大值

可以想到在遍历子树的时候
维护一个mx[i]mx[i] 记录当前节点到根节点经过i个【黑】点时的距离
处理出一个前缀最大值 然后就能O(k/2)的计算 当前最大值

但是问题时如何 避免以根节点儿子为根的子树中的不满足的值

笨想就是 枚举两个子树 然后维护，但显然这部分复杂度是O(n2)O(n^2)的

然后就像 其实对一个子树来说 就是要找它和除这个子树外的其他子树的最大值的和

对于n个子树来说 直接将前i-1的结果个合并,
然后就能直接维护第i个子树的答案了

然后这部分操作O([u].size()∗k)O([u].size()*k)

然后采用优化策略 只有,找到对每个以根节点儿子为根的子树中 经过最多的黑色点的路径中黑色点数为A,由于A大于K的地方对结果无贡献,就不用计算了, 这里算一个剪枝.

然后对前i-1个结果合并的时候 采取启发式合并,先合并小的,在合并大的,这样的话 维护下来mx[i]mx[i] 中ii的上届会递增,能够优化.

最后总复杂度就是O(nlog⁡n)O(n\log n) [详细复杂度分析请移步国家队论文↑]

附本题代码
——————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N = 200000+7;
const int INF = (~(1<<31));

inline int read(){
    int x=0,f=1;char ch = getchar();
    for(;ch<'0'||'9'<ch;ch=getchar()) if(ch=='-') f=-1;
    for(;'0'<=ch&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
    return x*f;
}

/*************************************************************/

int n,k,m,ans;

bool vis[N];
int black[N];

struct edge{
    int to,next;
    int w;
}G[N<<1];
int head[N],tot;
void add(int u,int v,int w=0){
    G[tot].w=w,G[tot].to=v,G[tot].next=head[u],head[u]=tot++;
}

/********重心 begin********/
int sz[N],dn[N],siz,zx;

void getzx(int u,int fa=0){
    sz[u]=1;dn[u]=0;
    for(int i=head[u],to;i!=-1;i=G[i].next){
        to = G[i].to;
        if(to == fa||vis[to]) continue;//puts("---+++---");
        getzx(to,u);
        sz[u]+=sz[to];
        dn[u]=max(dn[u],sz[to]);
    }
    dn[u]=max(dn[u],siz-sz[u]);
    if(dn[u]<dn[zx]) zx=u;
}

/*********重心 end********/

int dep[N],dis[N],deep_mx;
void getdis(int u,int fa=0){
	deep_mx=max(deep_mx,dep[u]);
	for(int i=head[u],to;i!=-1;i=G[i].next){
        to = G[i].to;
		if(vis[to]||to==fa)continue;
        dep[to]=dep[u]+black[to];
        dis[to]=dis[u]+G[i].w;
        getdis(to,u);
	}
}
int tmp[N],mx[N];
void getmx(int u,int fa=0){
	tmp[dep[u]]=max(tmp[dep[u]],dis[u]);
	for(int i=head[u],to;i;i=G[i].next){
        to = G[i].to;
		if(vis[to]||to==fa)continue;
        getmx(to,u);
	}
}

vector<pair<int,int> >v;
void solve(int u){
    vis[u]=1;if(black[u]) k--; v.clear();

    int l=0;
    for(int i=head[u],to;i!=-1;i=G[i].next){
        to=G[i].to; if(vis[to]) continue;
        deep_mx = 0;
        dep[to]=black[to];
        dis[to]=G[i].w;
        getdis(to,u);
        v.push_back(make_pair(deep_mx,to));
    }

    sort(v.begin(),v.end());

    for(int i=0,now;i<v.size();i++){
        getmx(v[i].second,u);
        now = 0;
        if(i){
            for(int j=v[i].first;j>=0;j--){
                while(now+j<k&&now<v[i-1].first)
                    now++,mx[now]=max(mx[now],mx[now-1]);
                if(now+j<=k) ans=max(ans,mx[now]+tmp[j]);
            }
        }
        if(i==v.size()-1){
            for(int j=0;j<=v[i].first;j++){
                if(j<=k) ans = max(max(tmp[j],mx[j]),ans);
                tmp[j]=mx[j]=0;
            }
        }
        else {
            for(int j=0;j<=v[i].first;j++)
                mx[j]=max(mx[j],tmp[j]),tmp[j]=0;
        }
    }
    if(black[u])k++;
    for(int i=head[u],to;i!=-1;i=G[i].next){
        to=G[i].to;
        if(vis[to]) continue;
        siz=sz[to],zx=0;getzx(to);
        solve(zx);
    }
}

int main(){
    memset(head,-1,sizeof(head));
   zx=0;  tot = 0;

    n=read(),k=read(),m=read();
    for(int i=1;i<=m;i++) black[read()]=1;

    for(int i=1,u,v,w;i<n;i++){
        u=read(),v=read(),w=read();
        add(u,v,w);add(v,u,w);
    }

    dn[0]=n;
    siz = n; getzx(1);
//    printf("tot = %d zx = %d\n",tot,zx);
//    for(int i=1;i<=n;i++)
//        printf("dn[%d] = %d sz[%d] = %d\n",i,dn[i],i,sz[i]);

    ans = 0; solve(zx);

    printf("%d\n",ans);
    return 0;
}