题解 TSM eerT

· · 个人记录

每个点向树上离他最远的点连边，这个显然。

一次操作之后就是直径两个端点连一条边，下面分别挂着一堆点的状态。

对于这个形态的树的操作，显然直径端点会分别从两边的点中产生，因为两个端点中间那条边是最大值。

就是取出两边的最大值，观察一下发现每边都加上了两个端点中间那条边的边权加另一边的最大值（两边的最大值除外），两个端点中间那条边加上两边的最大值，两边的最大值被替换成了最大值加原来两个端点中间那条边的边权。

（建议自己手玩一下）

有序性容易维护，初始排序一下，然后用队列模拟，再维护个加法标记。时间复杂度 O(n\log n+k)。

注意判断 -1。

fact：如果队列用 uint 存而且每次判断队列前两个是否相等会被卡，但是如果用 ull 存就不会，因为我没卡。赛时居然有人写双 hash 过了（就是维护另一个队列，另一个模数），也行。

讲个笑话，std 被 Sol1 hack 了（看评论区），欢迎大家继续 hack。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
namespace tokidosaya {
    typedef unsigned int ui;
    const int maxn=1e6+5;
    struct edge {
        int next,to,v;
    } e[maxn*2];
    int h[maxn],cnt,n,m,U,V,mp[maxn],bc[2],pd;
    ll md[maxn],mxd,d[2][maxn],b[2][maxn];
    ui tag[2];
    deque<ui> q[2];
    void addedge(int x,int y,int z) {
        e[++cnt].next=h[x],e[cnt].to=y,e[cnt].v=z,h[x]=cnt;
    }
    void dfs(int u,int fa) {
        ll mx1=0,mx2=-1;
        mp[u]=u;
        for(int i=h[u]; i; i=e[i].next) {
            int v=e[i].to;
            if(v==fa)continue;
            dfs(v,u);
            ll w=md[v]+e[i].v;
            if(mx1+w>mxd)mxd=mx1+w,U=mp[u],V=mp[v],pd=mx1==mx2||!mp[u]||!mp[v];
            else if(mx1+w==mxd)pd=1;
            if(w>mx1)mx1=w,mp[u]=mp[v];
            else if(w>mx2)mx2=w;
        }
        if(mx1==mx2)mp[u]=0;
        md[u]=mx1;
    }
    void bfs(int k) {
        queue<int> q;
        memset(d[k],-1,sizeof(d[k])),d[k][k?V:U]=0,q.push(k?V:U);
        while(!q.empty()) {
            int u=q.front();
            q.pop();
            for(int i=h[u]; i; i=e[i].next) {
                int v=e[i].to;
                if(!~d[k][v])d[k][v]=d[k][u]+e[i].v,q.push(v);
            }
        }
    }
    int main() {
        int x,y,z;
        n=read(),m=read();
        for(int i=2; i<=n; i++) {
            x=i-read(),z=read();
            addedge(x,i,z),addedge(i,x,z);
        }
        dfs(1,0),bfs(0),bfs(1);
        if(pd)return puts("-1"),0;

        ui now=mxd;
        for(int i=1; i<=n; i++) {
            if(i==U||i==V)continue;
//            cout<<d[0][i]<<' '<<d[1][i]<<'\n';
            if(d[0][i]==d[1][i])    return puts("-1"),0;
            else if(d[0][i]<d[1][i])b[1][++bc[1]]=d[1][i];
            else b[0][++bc[0]]=d[0][i];
        }
        for(int i=0; i<=1; i++) {
            sort(b[i]+1,b[i]+bc[i]+1);
            for(int j=bc[i]; j; j--) {
                if(b[i][j]==b[i][j+1]&&bc[i]-j<m)return puts("-1"),0;
                q[i].push_back(b[i][j]);
            }
        }
//        cout<<now<<'\n';
        bool pd0=q[0].empty(),pd1=q[1].empty();
        for(int k=2; k<=m; k++) {
//          if(q[0][0]==q[0][1]||q[1][0]==q[1][1])
//          {
//              cerr<<233;
//              for(;;);
//          }
            ui lm=pd0?0:q[0].front()+tag[0],rm=pd1?0:q[1].front()+tag[1];
//            cout<<now<<' '<<tag[0]<<' '<<lm<<' '<<tag[1]<<' '<<rm<<'\n';

            if(!pd0)q[0].pop_front(),q[0].push_back(-tag[0]);
            if(!pd1)q[1].pop_front(),q[1].push_back(-tag[1]);
            tag[0]+=now+rm,tag[1]+=now+lm,now+=lm+rm;
        }
        ui ans=0;
        for(int i=0; i<=1; i++)while(!q[i].empty())ans+=q[i].front()+tag[i],q[i].pop_front();
        printf("%u",ans+now);
        return 0;
    }
}
int main() {
    return tokidosaya::main();
}
/*
3 22
1 2 1
1 3 2

*/