题目
题目链接:https://www.luogu.com.cn/problem/P4319
小 w 和小 c 在 H 国,近年来,随着 H 国的发展,H 国的道路也在不断变化着。
根据 H 国的道路法,H 国道路都有一个值 \(w\),表示如果小 w 和小 c 通过这条道路,那么他们的 L 值会减少 \(w\),但是如果小 w 和小 c 在之前已经经过了这条路,那么他们的 L 值不会减少。
H 国有 \(N\) 个国家,最开始 H 国有 \(n-1\) 条道路,这 \(n-1\) 条道路刚好构成一棵树。
小 w 将和小 c 从 H 国的城市 1 出发,游览 H 国的所有城市,总共游览 32766 天,对于每一天,他们都希望游览结束后 L 值还是一个正数,那么他们出发时 L 值至少为多少。
H 国的所有边都是无向边,没有一条道路连接相同的一个城市。
\(n\leq 50000\)。
思路
就是给出一棵树,再给出若干条边,且后面给的每一条边只有在时间在区间 \([l,r]\) 内时才可以走。求每一天的最小生成树 \(+1\)。
有区间的限制并不是很好搞,所以考虑离线下来。
还是没什么想法,看题解。线段树分治 + LCT。mlgb 板子题。果然太菜了。
把每一个询问覆盖到线段树的 \(O(\log 32766)\) 区间上,然后 LCT 维护最小生成树即可。回溯时 cut 一下就好了。
时间复杂度 \(O(m\log m\log n)\)。其中 \(m=32766\)。
代码
喜提最劣解。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200010,M=32766;
int n,m,U[N],V[N];
ll ans;
struct node
{
int x,y;
};
struct LCT
{
#define lc ch[x][0]
#define rc ch[x][1]
int val[N],maxv[N],ch[N][2],fa[N];
bool rev[N];
bool pos(int x) { return x==ch[fa[x]][1]; }
bool notrt(int x) { return x==ch[fa[x]][0] || x==ch[fa[x]][1]; }
void pushup(int x)
{
int v1=val[x],v2=val[maxv[lc]],v3=val[maxv[rc]];
if (v1>=v2 && v1>=v3) maxv[x]=x;
if (lc && v2>=v1 && v2>=v3) maxv[x]=maxv[lc];
if (rc && v3>=v1 && v3>=v2) maxv[x]=maxv[rc];
}
void pushdown(int x)
{
if (rev[x])
{
swap(ch[lc][0],ch[lc][1]); rev[lc]^=1;
swap(ch[rc][0],ch[rc][1]); rev[rc]^=1;
rev[x]=0;
}
}
void rotate(int x)
{
int y=fa[x],z=fa[y],k=pos(x),c=ch[x][k^1];
if (notrt(y)) ch[z][pos(y)]=x; ch[x][k^1]=y; ch[y][k]=c;
if (c) fa[c]=y; fa[y]=x; fa[x]=z;
pushup(y); pushup(x);
}
void splay(int x)
{
stack<int> st; st.push(x);
for (int i=x;notrt(i);i=fa[i]) st.push(fa[i]);
for (;st.size();st.pop()) pushdown(st.top());
for (;notrt(x);rotate(x))
{
int y=fa[x];
if (notrt(y)) rotate(pos(x)==pos(y)?y:x);
}
}
void access(int x)
{
for (int y=0;x;y=x,x=fa[x])
{
splay(x); ch[x][1]=y;
pushup(x);
}
}
void makert(int x)
{
access(x); splay(x);
swap(lc,rc); rev[x]^=1;
}
void link(int x,int y)
{
makert(x); access(y); splay(y);
fa[x]=y; access(x);
}
void cut(int x,int y)
{
makert(x); access(y); splay(x);
ch[x][1]=fa[y]=0;
pushup(x);
}
#undef lc
#undef rc
}lct;
struct SegTree
{
vector<node> e[N];
stack<node> st;
void update(int x,int l,int r,int ql,int qr,node v)
{
if (ql<=l && qr>=r)
return (void)e[x].push_back(v);
int mid=(l+r)>>1;
if (ql<=mid) update(x*2,l,mid,ql,qr,v);
if (qr>mid) update(x*2+1,mid+1,r,ql,qr,v);
}
void query(int x,int l,int r)
{
int cnt=st.size();
for (int i=0;i<e[x].size();i++)
{
int w=e[x][i].x,id=e[x][i].y;
lct.makert(U[id]); lct.access(V[id]); lct.splay(V[id]);
if (lct.val[lct.maxv[V[id]]]>w)
{
int y=lct.maxv[V[id]];
ans=ans-lct.val[y]+w;
lct.cut(y,U[y]); lct.cut(y,V[y]);
lct.link(id,U[id]); lct.link(id,V[id]);
st.push((node){y,id});
}
}
if (l==r) cout<<ans+1<<"\n";
else
{
int mid=(l+r)>>1;
query(x*2,l,mid); query(x*2+1,mid+1,r);
}
for (;st.size()>cnt;st.pop())
{
int id1=st.top().x,id2=st.top().y;
ans=ans-lct.val[id2]+lct.val[id1];
lct.cut(id2,U[id2]); lct.cut(id2,V[id2]);
lct.link(id1,U[id1]); lct.link(id1,V[id1]);
}
}
}seg;
int main()
{
scanf("%d",&n);
for (int i=1;i<N;i++) lct.maxv[i]=i;
for (int i=1,x,y;i<n;i++)
{
scanf("%d%d%d",&x,&y,&lct.val[i+n]);
lct.link(x,i+n); lct.link(y,i+n);
ans+=lct.val[i+n];
U[i+n]=x; V[i+n]=y;
}
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
int u,v,l,r,w;
scanf("%d%d%d%d%d",&u,&v,&w,&l,&r);
lct.val[n*2+i]=w; U[n*2+i]=u; V[n*2+i]=v;
seg.update(1,1,M,l,r,(node){w,n*2+i});
}
seg.query(1,1,M);
return 0;
}