noip 2018 D1T3 赛道修建

noip 2018 D1T3 赛道修建

首先考虑二分答案，这时需要的就是对于一个长度求出能在树中选出来的最多的路径条数。考虑到一条路径是由一条向上的路径与一条向下的路径构成，或者仅仅是向上或向下的路径构成。

设\(f_i\)为i这颗子树中最多能选出来多少条路径，\(g_i\)为在i这颗子树内选出来\(f_i\)条路径后最多能往下延伸多么长的距离，就是以i点为端点向i的子树内可以选出来的最长的路径。

考虑一颗以i为根的子树，首先\(f_i=\sum_{j\in the\ son\ of\ i}f_j\)，然后对i的所有儿子的\(g_j+w_{i,j}\)排序，如果该值大于二分的答案，则直接将这个看成一条单独的路径一定不会更劣，那么直接将\(f_i\)加一。

然后从小到大枚举这个值，找到另一个最小的未被使用过的值使得两个数相加大于答案，并删掉这两个值。如果找不到这样的值，则用枚举的这个值更新\(g_i\)。

实现的时候可以用multiset，时间复杂度大概是\(O(nlog^2n)?\)

但是我的常数好大啊，在洛谷上开个O2就过了。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<set>

using namespace std;

const int Maxn=110000;

int to[Maxn],w[Maxn],nxt[Maxn],first[Maxn],f[Maxn],g[Maxn],tot=1;

int n,m,mid,u,v,wi;

inline void add(int u,int v,int wi) {

	to[tot]=v;

	w[tot]=wi;

	nxt[tot]=first[u];

	first[u]=tot++;

	to[tot]=u;

	w[tot]=wi;

	nxt[tot]=first[v];

	first[v]=tot++;

}

void work(int root,int fa) {

	f[root]=g[root]=0;

	multiset<int>se;

	vector<int>vi;

	for(int i=first[root];i;i=nxt[i])

		if(to[i]!=fa) {

			work(to[i],root);

			int temp=g[to[i]]+w[i];

			f[root]+=f[to[i]];

			if(temp>=mid) {

				f[root]++;

				continue;

			}

			vi.push_back(temp);

			se.insert(temp);

		}

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

	for(vector<int>::iterator i=vi.begin();i!=vi.end();i++)

		if(se.count(*i)) {

			se.erase(se.find(*i));

			multiset<int>::iterator j=se.lower_bound(mid-*i);

			if(j==se.end())

				g[root]=*i;

			else {

				f[root]++;

				se.erase(j);

			}

		}

}

int main() {

//	freopen("test.in","r",stdin);

	scanf("%d%d",&n,&m);

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

		scanf("%d%d%d",&u,&v,&wi);

		add(u,v,wi);

	}

	int l=1,r=0x3f3f3f3f;mid=100000;int ans=1;

	work(1,1);

	if(f[1]<m) r=99999;

	else l=100000,ans=100000;

	while(l<=r) {

//		memset(f,0,sizeof(f));

//		memset(g,0,sizeof(g));

		work(1,1);

		if(f[1]>=m) {

			ans=mid;

			l=mid+1;

		}

		else r=mid-1;

		mid=l+r>>1;

	}

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

	return 0;

}