「2021-10-28 提高模拟赛」小 w 与最长路

题目链接

题意

给定一棵树，边有边权，对于每条边求删掉它再用它连成一棵树后直径的最小值。

思路

先提取出直径，非直径边操作后该直径仍为答案，直径边操作后一定连接两棵树的中心。

即，最后连出的新树直径只有两种可能：

1. 是 $S$ 所在的树或 $T$ 所在的树的直径；
2. 经过两棵树的中心，由新加进去的边连接。

设直径端点为 $S,T$，把它拉成一条横线（$S$ 在左），其中每个点连出一些子树。

现在断掉 $(u,v)$（设 $u$ 与 $S$ 同侧，只考虑它们所在的树），有个结论：
$S$ 所在的树的中点一定在 $S$ 到 $u$ 的路径上。

那如何维护直径？
这棵树的直径一定是 $S$ 向右走到某个特殊点然后进入它的子树，走完最长链。
设 $lnk_x$ 为 $x$ 子树内最长链长度，我们只要扫一遍 $x$，找到最大的 $dis(S,x)+lnk_x$，该点即为特殊点。

当从左到右操作直径边时，$x$ 也从左到右移动，所以复杂度很正确。
至于中心，扫 $x$ 的时候顺带维护即可。

对于 $T$ 所在树也做同样一遍操作，最后合并即可。

实现

注意扫直径边时需确认 $u$ 在 $S$ 一侧。

时空复杂度 $\mathcal O(n)$。

代码

#include<cstdio>
#include<vector>
using namespace std;
typedef pair<int,int> pii;
const int N=2e6,mod=998244353;
int n;
struct edge {
    int u,v,w;
} edg[N];
vector<pii> e[N+1];
int s,t;
vector<int> d;
int did[N+1];
long long ds[N+1],dt[N+1];
long long lnk[N+1],tds[N+1],tdt[N+1];
long long f[N+1],g[N+1];
int res;
void addEdge(int id,int u,int v,int w)
{
    edg[id]=edge{u,v,w};
    e[u].push_back(pii(v,w)),e[v].push_back(pii(u,w));
    return;
}
void generate()
{
    int F,W;
    unsigned long long seed;
    auto rand=[&seed]()->unsigned long long {
        seed^=seed<<13,seed^=seed>>17,seed^=seed<<5;
        return seed;
    };
    scanf("%llu%d%d",&seed,&F,&W);
    for(int i=1,f,w;i<n;++i) {
        f=rand()%min(i,F)+i-min(i,F)+1;
        w=rand()%W;
        addEdge(i,f,i+1,w);
    }
    return;
}
void calcDis(int u,int f,long long d[])
{
    for(auto [v,w]:e[u]) {
        if(v!=f) {
            d[v]=d[u]+w;
            calcDis(v,u,d);
        }
    }
    return;
}
bool extractDiameter(int u,int f)
{
    if(u==s) {
        d.push_back(u);
        return true;
    }
    for(auto [v,w]:e[u]) {
        if((v!=f)&&extractDiameter(v,u)) {
            d.push_back(u);
            return true;
        }
    }
    return false;
}
void findDiameter()
{
    calcDis(1,0,ds);
    for(int i=1;i<=n;++i) {
        if(ds[i]>ds[s]) {
            s=i;
        }
    }
    ds[s]=0,calcDis(s,0,ds);
    for(int i=1;i<=n;++i) {
        if(ds[i]>ds[t]) {
            t=i;
        }
    }
    calcDis(t,0,dt);
    extractDiameter(t,0);
    for(int i=0;i<d.size();++i) {
        did[d[i]]=i+1;
    }
    return;
}
long long calcTd(int u,int f,long long td[])
{
    long long fl=0,sl=0;
    for(auto [v,w]:e[u]) {
        if(v==f) {
            continue;
        }
        long long nl=calcTd(v,u,td)+w;
        if(nl>fl) {
            swap(fl,nl);
        }
        if(nl>sl) {
            swap(sl,nl);
        }
        td[u]=max(td[u],td[v]);
    }
    td[u]=max(td[u],fl+sl);
    return fl;
}
long long calcLnk(int u,int f)
{
    long long r=0;
    for(auto [v,w]:e[u]) {
        if((v!=f)&&!did[v]) {
            r=max(r,calcLnk(v,u)+w);
        }
    }
    return r;
}
template<class T>
void calcF(T beg,T end,long long d[],long long f[])
{
    for(T it=beg+1,x=beg,c=beg;it!=end;++it) {
        if(d[*it]+lnk[*it]>d[*x]+lnk[*x]) {
            x=it;
            long long t=d[*it]+lnk[*it];
            while((c!=it)&&(max(d[*(c+1)],t-d[*(c+1)])<=max(d[*c],t-d[*c]))) {
                ++c;
            }
        }
        f[*it]=max(d[*c],d[*x]+lnk[*x]-d[*c]);
    }
    return;
}
int main()
{
    freopen("path.in","r",stdin);
    freopen("path.out","w",stdout);
    scanf("%d",&n);
    generate();
    findDiameter();
    calcTd(t,0,tds),calcTd(s,0,tdt);
    for(int it:d) {
        lnk[it]=calcLnk(it,0);
    }
    calcF(d.begin(),d.end()-1,ds,f),calcF(d.rbegin(),d.rend()-1,dt,g);
    for(int i=1;i<n;++i) {
        int u=edg[i].u,v=edg[i].v;
        if(did[u]&&did[v]) {
            if(did[u]>did[v]) {
                swap(u,v);
            }
            res^=max(max(tds[u],tdt[v]),f[u]+g[v]+edg[i].w)%mod*i%mod;
        } else {
            res^=ds[t]%mod*i%mod;
        }
    }
    printf("%d\n",res);
    return 0;
}