TYB之边路打野，第一次模拟赛，树的直径+LCA

正题

      众所周知，队长tyb天天看主力队员ozy打王者。有一天，他突然觉得无聊了，于是开发出船新版本，王者农药之打野英雄传。简单来说，深谙oi的tyb队长将地图做成N个点的树，在每条树边上有wi的野怪。因为ozy不屑于做重复的题，所以他每次出发都会走简单路线，即每条边最多经过一次。ozy刚从王者一路连跪到青铜，忙着上分，没时间研究tyb的地图。现在他想知道，从xi出发，最多能打多少野怪。

      这道题的数据是很大的都是1000000.

      我们有一个结论，一个点在一棵树上的最长距离，另一端一定在树的直径的两个端点上。而树的直径可以从树上的任意一个节点every出发，找最远端点x，再从最远端点x出发，找x的最远端点y即可。

      那么我们看一下怎么把这个东西搞出来。

      我们做两遍dfs，一次从1点开始，把一棵树提起来找出最长那条边的端点，记录下来。

      然后从那个端点开始，找最远的一个端点，那么找出来的这两个端点就是树的直径（不要问我为什么我也不知道，因为我菜啊），我们搞一个倍增来维护当前节点到父亲的距离，每次在当前点与x或y的距离取最大即可。

#include
#include
#includeint n,m;
char s[21][100010];
bool tf[21];
int mmin=1e9;void dfs(int x){int ans=0;for(int i=1;i<=m;i++){int tot=0;for(int j=1;j<=n;j++)if(s[j][i]=='1') tot++;if(tot>n/2) ans+=n-tot;  else ans+=tot;}if(ans

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！