FTOUR2 - Free tour II

题目翻译的很清楚……似乎点分治的题题目描述都非常简洁。

还是那个操作，一条路径要么全部在一棵子树中，要么经过当前的重心，所以考虑点分治。

首先dfs求出重心的每一棵子树中，有i个黑点的最长路径长度（这个没什么难度），之后我们只要考虑一下怎么在子树之内合并信息即可。

首先我们肯定是枚举所有的子树，用已经枚举过的s-1个子树的答案去和当前子树的答案合并更新新的答案，并且更新当前最大值。但是直接合并的复杂度很大，需要进行启发式合并。我们可以首先记录一下每棵子树的最大深度，之后把他们按照最大深度从小到大排序，之后对于每一个子树，倒叙枚举其内部黑点个数。因为我们是需要枚举前s-1棵子树内的黑点个数来合并路径的，如果正序枚举，我们每次都需要枚举前s-1棵子树内很多个黑点个数，之后还得重新回来枚举。但是倒叙的话，后来的值就可以直接被用上了。而且我们只需要枚举到前一棵的最大黑点个数，因为肯定不会有更多的了。

而至于后面的值的更新，虽然看起来是两层循环，但是肯定不会超过节点个数，所以是O（n）的。

这样的话我们的合并就变成了nlogn的，于是总复杂度就是O（nlog²n），可以通过。

其实感觉点分治的题……算法都是能想到的……但是不知道怎么实现。

看一下代码。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<set>

#include<vector>

#include<map>

#include<queue>

#define rep(i,a,n) for(int i = a;i <= n;i++)

#define per(i,n,a) for(int i = n;i >= a;i--)

#define enter putchar('\n')

#define fr friend inline

#define y1 poj

#define mp make_pair

#define pr pair<int,int>

#define fi first

#define sc second

#define pb push_back

#define lowbit(x) x & (-x)

#define B printf("Bug\n");

using namespace std;

typedef long long ll;

const int M = ;

const int N = ;

const int INF = 1e9;

const double eps = 1e-;

int read()

{

    int x = ,op = ;char ch = getchar();

    while(ch < '' || ch > '') {if(ch == '-') op = -;ch = getchar();}

    while(ch >= '' && ch <= '') x = x *  + ch - '',ch = getchar();

    return x * op;

}

struct edge

{

   int next,to,from,v;

}e[M<<];

int n,k,m,maxn[M],G,size[M],dis[M],dep[M],sum,x,y,z,head[M],ecnt,hson[M],ans,tmp[M],mdep;

bool black[M],vis[M];

vector <pr> v;

void add(int x,int y,int z)

{

   e[++ecnt].to = y;

   e[ecnt].next = head[x];

   e[ecnt].from = x;

   e[ecnt].v = z;

   head[x] = ecnt;

}

void getG(int x,int fa)//找重心

{

   size[x] = ,hson[x] = ;

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

   {

      if(e[i].to == fa || vis[e[i].to]) continue;

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

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

   }

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

   if(hson[x] < hson[G]) G = x;

}

void getdis(int x,int fa,int d,int depth)//获取子树内路径长度和经过的黑点个数

{

   dis[x] = d,dep[x] = depth,mdep = max(mdep,dep[x]);

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

   {

      if(e[i].to == fa || vis[e[i].to]) continue;

      getdis(e[i].to,x,d + e[i].v,depth + black[e[i].to]);

   }

}

void getmaxn(int x,int fa)//用第s棵子树的值更新当前值

{

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

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

   {

      if(vis[e[i].to] || e[i].to == fa) continue;

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

   }

}

void solve(int x)

{

   vis[x] = ,v.clear();

   if(black[x]) k--;//如果这个点是黑点要--

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

   {

      if(vis[e[i].to]) continue;

      mdep = ,getdis(e[i].to,x,e[i].v,black[e[i].to]);

      v.pb(mp(mdep,e[i].to));

   }//计算每棵子树内部情况

   sort(v.begin(),v.end());//按最大深度排序

   rep(i,,(int)(v.size()-))

   {

      getmaxn(v[i].sc,x);

      int cur = ;

      if(i != )

      per(j,v[i].fi,)

      {

     while(cur + j < k && cur < v[i-].fi) cur++,maxn[cur] = max(maxn[cur],maxn[cur-]);//用黑点数少的更新多的

     if(cur + j <= k) ans = max(ans,maxn[cur] + tmp[j]);//合并，更新答案

      }

      if(i != v.size() - ) rep(j,,v[i].fi) maxn[j] = max(maxn[j],tmp[j]),tmp[j] = ;

      else rep(j,,v[i].fi){if(j <= k) ans = max(ans,max(tmp[j],maxn[j]));tmp[j] = maxn[j] = ;}//更新值和答案（注意在末尾的时候要把两个数组都清零，为以后递归求解用）

   }

   if(black[x]) k++;//还原

   for(int i = head[x];i;i = e[i].next)//递归求解子树内情况

   {

      if(vis[e[i].to]) continue;

      sum = size[e[i].to],G = ;

      getG(e[i].to,x),solve(G);

   }

}

int main()

{

   n = read(),k = read(),m = read();

   rep(i,,m) x = read(),black[x] = ;

   rep(i,,n-) x = read(),y = read(),z = read(),add(x,y,z),add(y,x,z);

   sum = n,hson[G] = INF,getG(,);

   solve(G);

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

   return ;

}

巴特西

FTOUR2 - Free tour II

最新文章

热门文章