前言
好家伙，严格一个 (log_2m) 竟然比 (log_2^2n) 慢！
题目
讲解
刨开树边不看，我们看非树边的贡献。
对于非树边 ((u,v,w))，显然它可以对 (u ightarrow v) 路径上除 LCA 的点产生贡献，可以试图用 (dis_u+dis_v+w-dis_x) 去更新路径上点 (x) 的答案。
有一个做法是直接树剖+线段树，时间复杂度是 (O(mlog_2^2n)) 的(169ms~789ms)。
我的做法是在 (u) 和 (v) 两个点用可并堆打个标记，在 LCA 处打两个删除标记，然后自底向上合并即可，时间复杂度 (O(mlog_2m))，喜提倒数第二(996ms)。
然后我们康康 rk1(88ms) 的代码
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) x=fa[x];
while(x!=y) x=fa[x],y=fa[y];
return x;
}
void calc(int x,int y,int w,int z){
int now=x,d=dis[y]+w;
while(now!=z){
ans[now]=min(ans[now],d);
d+=wt[now],now=fa[now];
}
now=y,d=dis[x]+w;
while(now!=z){
ans[now]=min(ans[now],d);
d+=wt[now],now=fa[now];
}
}
好家伙全是暴力跳的。
代码
这题数据真不错
//12252024832524
#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 4005;
const int MAXM = 100005;
const int INF = 0x3f3f3f3f;
int n,m,ans[MAXN];
LL Read()
{
LL x = 0,f = 1; char c = getchar();
while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int head[MAXN],etot;
struct edge
{
int v,w,nxt;
}e[MAXN << 1];
void Add_Edge(int x,int y,int z)
{
e[++etot] = edge{y,z,head[x]};
head[x] = etot;
}
void Add_Double_Edge(int x,int y,int z)
{
Add_Edge(x,y,z);
Add_Edge(y,x,z);
}
int letot;
struct LeftEdge
{
int u,v,w;
}le[MAXM];
int f[MAXN],d[MAXN],siz[MAXN],son[MAXN],dis[MAXN];
void dfs1(int x,int fa)
{
siz[x] = 1; d[x] = d[fa] + 1; f[x] = fa;
for(int i = head[x],v; i ;i = e[i].nxt)
{
v = e[i].v;
if(v == fa) continue;
dis[v] = dis[x] + e[i].w;
dfs1(v,x);
siz[x] += siz[v];
if(siz[v] > siz[son[x]]) son[x] = v;
}
}
int tp[MAXN];
void dfs2(int x,int t)
{
tp[x] = t;
if(!son[x]) return;
dfs2(son[x],t);
for(int i = head[x],v; i ;i = e[i].nxt)
{
v = e[i].v;
if(v == f[x] || v == son[x]) continue;
dfs2(v,v);
}
}
int lca(int u,int v)
{
while(tp[u]^tp[v])
{
if(d[tp[u]] < d[tp[v]]) swap(u,v);
u = f[tp[u]];
}
return d[u] < d[v] ? u : v;
}
int tot,rt[MAXN << 1],val[MAXM << 2],dist[MAXM << 2],ch[MAXM << 2][2];
int nn(int v)//newnode
{
val[++tot] = v;
return tot;
}
int mge(int x,int y)
{
if(!x || !y) return x | y;
if(val[x] > val[y]) swap(x,y);
ch[x][1] = mge(ch[x][1],y);
if(dist[ch[x][0]] < dist[ch[x][1]]) swap(ch[x][0],ch[x][1]);
dist[x] = dist[ch[x][1]] + 1;
return x;
}
void Pop(int &x){x = mge(ch[x][0],ch[x][1]);}
void dfs3(int x)
{
for(int i = head[x],v; i ;i = e[i].nxt)
{
v = e[i].v;
if(v == f[x]) continue;
dfs3(v);
rt[x] = mge(rt[x],rt[v]);
rt[x+n] = mge(rt[x+n],rt[v+n]);
}
while(rt[x] && rt[x+n] && val[rt[x]] == val[rt[x+n]]) Pop(rt[x]),Pop(rt[x+n]);
if(rt[x]) ans[x] = val[rt[x]] - dis[x];
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read(); m = Read();
for(int i = 1;i <= m;++ i)
{
int u = Read(),v = Read(),w = Read(),opt = Read();
if(opt) Add_Double_Edge(u,v,w);
else le[++letot] = LeftEdge{u,v,w};
}
dfs1(1,0);
dfs2(1,1);
for(int i = 1;i <= letot;++ i)
{
int cur = dis[le[i].u] + dis[le[i].v] + le[i].w,LCA = lca(le[i].u,le[i].v);
rt[LCA+n] = mge(mge(rt[LCA+n],nn(cur)),nn(cur));
rt[le[i].u] = mge(rt[le[i].u],nn(cur));
rt[le[i].v] = mge(rt[le[i].v],nn(cur));
}
for(int i = 2;i <= n;++ i) ans[i] = INF;
dfs3(1);
for(int i = 2;i <= n;++ i) Put(ans[i] == INF ? -1 : ans[i],i == n ? '
' : ' ');
return 0;
}