[WC2018]通道（乱搞，迭代）

[洛谷题面]https://www.luogu.org/problemnew/show/P4221

这个题以及[CTSC2018 暴力写挂]都有类似的乱搞做法能通过考场数据。

具体搞法就是随一个起点，找一个离他最远（按题目要求计算的贡献最大）的点，让后再令 \(now=mxpoint\) 不断迭代上述过程。
然后整个上述过程最好也要不断重复进行，直到卡满时限为止就好。
多调随机种子就好。

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
using ll=long long;
const int N=100005;
int rr()
{
    return rand()%10000*10000+rand()%10000;
}
struct node
{
    int tot,h[N],nxt[N<<1],to[N<<1];
    ll dis[N],w[N<<1];
    void addedge(int u,int v,ll _w) {
        nxt[++tot]=h[u]; h[u]=tot;
        to[tot]=v; w[tot]=_w;
        nxt[++tot]=h[v]; h[v]=tot;
        to[tot]=u; w[tot]=_w;
    }
    int sz[N],dep[N],son[N];
    int fa[N],top[N];
    void dfs(int u,int father)
    {
        sz[u]=1;
        fa[u]=father;
        for(int i=h[u],v;i;i=nxt[i])
        {
            v=to[i];
            if(v!=father)
            {
                dep[v]=dep[u]+1;
                dis[v]=dis[u]+w[i];
                dfs(v,u);
                sz[u]+=sz[v];
                if(sz[v]>sz[son[u]])son[u]=v;
            }
        }
    }
    void pul(int u,int Top)
    {
        top[u]=Top;
        if(son[u])pul(son[u],Top);
        for(int i=h[u],v;i;i=nxt[i])
        {
            v=to[i];
            if(v!=fa[u]&&v!=son[u])
                pul(v,v);
        }
    }
    int lca(int u,int v)
    {
        while(top[u]!=top[v])
        {
            if(dep[top[u]]<dep[top[v]])
                swap(u,v);
            u=fa[top[u]];
        }
        return dep[u]<dep[v]?u:v;
    }
    ll dist(int u,int v)
    {
        return dis[u]+dis[v]-dis[lca(u,v)]*2;
    }
}a[3];
int n;
ll dist(int i,int j)
{
    return a[0].dist(i,j)+a[1].dist(i,j)+a[2].dist(i,j);
}
ll ans;
int main()
{
    scanf("%d",&n);
    int x,y; ll z;
    for(int k=0;k<3;k++)
    {
        for(int i=2; i<=n; i++)
        {
            scanf("%d%d%lld",&x,&y,&z);
            a[k].addedge(x,y,z);
        }
        a[k].dfs(1,0);
        a[k].pul(1,1);
    }
    if(n <= 3000)
    {
        for(int i=1; i<=n; i++)
            for(int j=i+1; j<=n; j++)
                ans=max(ans,dist(i,j));
    }
    else
    {
        for(int k=0; k<40; k++)
        {
            int now=rr()%n+1;
            for(int i=0,j; i<5; i++)
            {
                ll mx=-1;
                for(int l=1; l<=n; l++)
                {
                    ll ext=dist(now,l);
                    if(ext>mx)
                    {
                        mx=ext;
                        j=l;
                    }
                }
                ans=max(ans,mx);
                now=j;
            }
        }
    }
    printf("%lld",ans);
    return 0;
}

[WC2018]通道（乱搞，迭代）

原文：https://www.cnblogs.com/bestwyj/p/10902754.html