「SPOJ1825」Free tour II

2015年1月1日5,1363

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 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

1 3 1

2 3 10

3 4 -2

4 5 -1

5 7 6

5 6 5

4 8 3

Output:

题解

设路径起点为根，终点为x的路径，经过黑色结点数量为deep[x]，路径长度为dis[x]
考虑解决经过根的路径,递归子树处理其它路径。
依次处理root的每棵子树,处理到子树S的时候，我们需要知道出发点为根，终点在前S-1棵子树子树中，经过t(t<K)个黑点的路径的最长长度,记为mx[t]
则对于子树S的结点x\[mx[t]+dis[x](deep[x]+t\leq K)\xrightarrow{update} ans\]（若根为黑色处理时将K–，处理完恢复）若按照deep倒序处理每个结点，mx指针now按照升序扫，则\(mx[now-1]\xrightarrow{update} mx[now]\)，这样就能得到符合条件的mx[t]的最大值。
然后再考虑用子树S的信息更新mx，将两个数组合并的操作次数是\(max(L1,L2)\)，可以考虑按照每棵子树deep的升序依次合并子树。从总体来看，由于总边数是n-1，则排序的复杂度nlogn，同时这样启发式合并使得合并的复杂度降为nlogn

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int ans;
int n,K,m,cnt;
int rt,sum,deep_mx;
int last[200005],size[200005],f[200005],deep[200005],dis[200005];
bool color[200005],vis[200005];
vector<pair<int,int> >st;
int tmp[200005],mx[200005];
struct edge{
	int to,next,v;
}e[400005];
void insert(int u,int v,int w)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;
}
void getroot(int x,int fa)
{
	size[x]=1;f[x]=0;
	for(int i=last[x];i;i=e[i].next)
		if(!vis[e[i].to]&&e[i].to!=fa)
		{
			getroot(e[i].to,x);
			f[x]=max(f[x],size[e[i].to]);
			size[x]+=size[e[i].to];
		}
	f[x]=max(f[x],sum-size[x]);
	if(f[x]<f[rt])rt=x;
}
void getdis(int x,int fa)
{
	deep_mx=max(deep_mx,deep[x]);
	for(int i=last[x];i;i=e[i].next)
		if(!vis[e[i].to]&&e[i].to!=fa)
		{
			deep[e[i].to]=deep[x]+color[e[i].to];
			dis[e[i].to]=dis[x]+e[i].v;
			getdis(e[i].to,x);
		}
}
void getmx(int x,int fa)
{
	tmp[deep[x]]=max(tmp[deep[x]],dis[x]);
	for(int i=last[x];i;i=e[i].next)
		if(!vis[e[i].to]&&e[i].to!=fa)
			getmx(e[i].to,x);
}
void solve(int x)
{
	vis[x]=1;st.clear();
	if(color[x])K--;
	for(int i=last[x];i;i=e[i].next)
		if(!vis[e[i].to])
		{
			deep_mx=0;
			deep[e[i].to]=color[e[i].to];
			dis[e[i].to]=e[i].v;
			getdis(e[i].to,x);
			st.push_back(make_pair(deep_mx,e[i].to));
		}
	sort(st.begin(),st.end());
	for(int i=0;i<st.size();i++)
	{
		getmx(st[i].second,x);
		int now=0;
		if(i!=0)
			for(int j=st[i].first;j>=0;j--)
			{
				while(now+j<K&&now<st[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!=st.size()-1)
			for(int j=0;j<=st[i].first;j++)
				mx[j]=max(mx[j],tmp[j]),tmp[j]=0;
		else 
			for(int j=0;j<=st[i].first;j++)
			{
				if(j<=K)ans=max(ans,max(tmp[j],mx[j]));
				tmp[j]=mx[j]=0;
			}
	}
	if(color[x])K++;
	for(int i=last[x];i;i=e[i].next)
		if(!vis[e[i].to])
		{
			rt=0;sum=size[e[i].to];
			getroot(e[i].to,x);
			solve(rt);
		}
}
int main()
{
	n=read();K=read();m=read();
	for(int i=1;i<=m;i++)
	{
		int x=read();
		color[x]=1;
	}
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read(),w=read();
		insert(u,v,w);
	}
	sum=n;f[0]=n;
	getroot(1,0);
	solve(rt);
	printf("%d\n",ans);
	return 0;
}

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

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int ans;

int n,K,m,cnt;

int rt,sum,deep_mx;

int last[200005],size[200005],f[200005],deep[200005],dis[200005];

bool color[200005],vis[200005];

vector<pair<int,int> >st;

int tmp[200005],mx[200005];

struct edge{

int to,next,v;

}e[400005];

void insert(int u,int v,int w)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;

}

void getroot(int x,int fa)

{

size[x]=1;f[x]=0;

for(int i=last[x];i;i=e[i].next)

if(!vis[e[i].to]&&e[i].to!=fa)

{

getroot(e[i].to,x);

f[x]=max(f[x],size[e[i].to]);

size[x]+=size[e[i].to];

}

f[x]=max(f[x],sum-size[x]);

if(f[x]<f[rt])rt=x;

}

void getdis(int x,int fa)

{

deep_mx=max(deep_mx,deep[x]);

for(int i=last[x];i;i=e[i].next)

if(!vis[e[i].to]&&e[i].to!=fa)

{

deep[e[i].to]=deep[x]+color[e[i].to];

dis[e[i].to]=dis[x]+e[i].v;

getdis(e[i].to,x);

}

void getmx(int x,int fa)

{

tmp[deep[x]]=max(tmp[deep[x]],dis[x]);

for(int i=last[x];i;i=e[i].next)

if(!vis[e[i].to]&&e[i].to!=fa)

getmx(e[i].to,x);

}

void solve(int x)

{

vis[x]=1;st.clear();

if(color[x])K--;

for(int i=last[x];i;i=e[i].next)

if(!vis[e[i].to])

{

deep_mx=0;

deep[e[i].to]=color[e[i].to];

dis[e[i].to]=e[i].v;

getdis(e[i].to,x);

st.push_back(make_pair(deep_mx,e[i].to));

}

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

for(int i=0;i<st.size();i++)

{

getmx(st[i].second,x);

int now=0;

if(i!=0)

for(int j=st[i].first;j>=0;j--)

{

while(now+j<K&&now<st[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!=st.size()-1)

for(int j=0;j<=st[i].first;j++)

mx[j]=max(mx[j],tmp[j]),tmp[j]=0;

else

for(int j=0;j<=st[i].first;j++)

{

if(j<=K)ans=max(ans,max(tmp[j],mx[j]));

tmp[j]=mx[j]=0;

}

if(color[x])K++;

for(int i=last[x];i;i=e[i].next)

if(!vis[e[i].to])

{

rt=0;sum=size[e[i].to];

getroot(e[i].to,x);

solve(rt);

}

int main()

{

n=read();K=read();m=read();

for(int i=1;i<=m;i++)

{

int x=read();

color[x]=1;

}

for(int i=1;i<n;i++)

{

int u=read(),v=read(),w=read();

insert(u,v,w);

}

sum=n;f[0]=n;

getroot(1,0);

solve(rt);

printf("%d\n",ans);

return 0;

}

« 「BZOJ4016」[FJOI2014] 最短路径树问题「点分治练习」boatherds »

lihs

那个应该是t+deep <=k 吧

试一下这个
2 0 0
1 2 1

hzwer

已改正

hzwer.com _ Home | http://hzwer.com

「SPOJ1825」Free tour II

Input

Output

Example

分类目录

热门文章

Myfriends

近期评论