最近学了一下线段树分治,感觉还蛮好用...

如果正常动态维护最大生成树的话用 LCT 就行,但是这里还有时间这一维的限制.

所以,我们就把每条边放到以时间为轴的线段树的节点上,然后写一个可撤销 LCT 就好了 ~

code:

#include <bits/stdc++.h>
#define RM 32766
#define N 2000005
#define ll long long
#define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout)
using namespace std;
namespace LCT
{
#define lson t[x].ch[0]
#define rson t[x].ch[1]
struct node
{
ll sum;
int f,ch[2],rev,w,maxx,id;
}t[N];
int sta[N];
inline int get(int x) { return t[t[x].f].ch[1]==x; }
inline int Irt(int x) { return !(t[t[x].f].ch[0]==x||t[t[x].f].ch[1]==x); }
inline void mark(int x)
{
if(!x) return;
swap(lson,rson), t[x].rev^=1;
}
inline void pushdown(int x)
{
if(x&&t[x].rev)
{
if(lson) mark(lson);
if(rson) mark(rson);
t[x].rev=0;
}
}
inline void pushup(int x)
{
t[x].id=x;
t[x].sum=t[x].w;
t[x].maxx=t[x].w;
if(lson)
{
t[x].sum+=t[lson].sum;
if(t[lson].maxx>t[x].maxx)
{
t[x].id=t[lson].id;
t[x].maxx=t[lson].maxx;
}
}
if(rson)
{
t[x].sum+=t[rson].sum;
if(t[rson].maxx>t[x].maxx)
{
t[x].id=t[rson].id;
t[x].maxx=t[rson].maxx;
}
}
}
inline void rotate(int x)
{
int old=t[x].f,fold=t[old].f,which=get(x);
if(!Irt(old)) t[fold].ch[t[fold].ch[1]==old]=x;
t[old].ch[which]=t[x].ch[which^1], t[t[old].ch[which]].f=old;
t[x].ch[which^1]=old,t[old].f=x,t[x].f=fold;
pushup(old), pushup(x);
}
inline void splay(int x)
{
int u=x,v=0,fa;
for(sta[++v]=u;!Irt(u);u=t[u].f) sta[++v]=t[u].f;
for(;v;--v) pushdown(sta[v]);
for(u=t[u].f;(fa=t[x].f)!=u;rotate(x)) if(t[fa].f!=u) rotate(get(fa)==get(x)?fa:x);
}
inline void Access(int x)
{
for(int y=0;x;y=x,x=t[x].f) splay(x),rson=y,pushup(x);
}
inline void MakeRT(int x)
{
Access(x),splay(x),mark(x);
}
inline void Link(int x,int y)
{
MakeRT(y),t[y].f=x;
}
inline void split(int x,int y)
{
MakeRT(x),Access(y),splay(y);
}
inline void cut(int x,int y)
{
MakeRT(y),Access(x),splay(x);
t[x].ch[0]=t[y].f=0;
pushup(x);
}
inline int findroot(int x)
{
for(Access(x),splay(x);lson;x=lson);
return x;
}
#undef lson
#undef rson
};
#define lson now<<1
#define rson now<<1|1
int n;
int tag[N];
vector<int>G[N<<2];
struct edge
{
int u,v,w;
edge(int u=0,int v=0,int w=0):u(u),v(v),w(w){}
}e[N];
struct E
{
int u,op;
E(int u=0,int op=0):u(u),op(op){}
};
void Modify(int l,int r,int now,int L,int R,int id)
{
if(l>=L&&r<=R)
{
G[now].push_back(id);
return;
}
int mid=(l+r)>>1;
if(L<=mid) Modify(l,mid,lson,L,R,id);
if(R>mid) Modify(mid+1,r,rson,L,R,id);
}
void solve(int l,int r,int now,ll pre)
{
stack<E>S;
for(int i=0;i<G[now].size();++i)
{
int id=G[now][i];
int u=e[id].u,v=e[id].v,w=e[id].w;
int _new=id+n;
if(LCT::findroot(u)!=LCT::findroot(v))
{
LCT::t[_new].w=w;
LCT::Link(u,_new);
LCT::Link(_new,v);
pre+=1ll*w;
S.push(E(_new,0));
}
else
{
LCT::split(u,v);
if(LCT::t[v].maxx>w)
{
pre=pre-LCT::t[v].maxx+w;
int tmp=LCT::t[v].id;
LCT::cut(tmp,e[tmp-n].u);
LCT::cut(tmp,e[tmp-n].v);
LCT::t[_new].w=w;
LCT::Link(u,_new);
LCT::Link(_new,v);
S.push(E(tmp,1));
S.push(E(_new,0));
}
}
}
if(l==r) printf("%lld\n",pre+1);
else
{
int mid=(l+r)>>1;
if(l<=mid) solve(l,mid,lson,pre);
if(r>mid) solve(mid+1,r,rson,pre);
}
while(!S.empty())
{
E pp=S.top(); S.pop();
if(pp.op==0)
{
LCT::cut(pp.u,e[pp.u-n].u);
LCT::cut(pp.u,e[pp.u-n].v);
}
else
{
LCT::t[pp.u].w=e[pp.u-n].w;
LCT::Link(pp.u,e[pp.u-n].u);
LCT::Link(pp.u,e[pp.u-n].v);
}
}
}
#undef lson
#undef rson
int main()
{
// setIO("input");
int i,j,m;
scanf("%d",&n);
for(i=1;i<n;++i)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
e[i]=edge(u,v,w);
Modify(1,RM,1,1,RM,i);
}
scanf("%d",&m);
for(i=1;i<=m;++i)
{
int u,v,w,l,r;
scanf("%d%d%d%d%d",&u,&v,&w,&l,&r), e[n+i-1]=edge(u,v,w), Modify(1,RM,1,l,r,n+i-1);
}
solve(1,RM,1,0ll);
return 0;
}

  

最新文章

  1. 利用JSONP实现跨域请求
  2. Net分布式系统之二:CentOS系统搭建Nginx负载均衡(下)
  3. 修改Tomcat服务器的默认端口号
  4. NAT,网络地址转换详解
  5. HDOJ --- 1176 免费馅饼
  6. TI-Davinci开发系列之二使用CCS5.2TI Simulator模拟环境调试DSP程序
  7. D题(贪心)
  8. 谁能告诉我为什么sum_area输出总是0(多边形重心问题)
  9. dom4j生成和解析xml文件
  10. 搭建subversion 服务器,并自动部署项目
  11. 美团--Quake全链路压测平台
  12. 锤子科技&quot;临死前&quot;被&quot;接盘&quot; ,内部人士爆料已改签今日头条母公司
  13. 分析轮子(二)- &lt;&lt; ,&gt;&gt;,&gt;&gt; (左移、右移、无符号右移)
  14. 创建一个dynamics 365 CRM online plugin (二) - fields检查
  15. 关于web优化(一)
  16. Android Handler面试解析
  17. c++ primer 学习杂记2【派生类到基类转换的可访问性】
  18. killall 、kill 、pkill 命令详解 【转】
  19. kaggle 欺诈信用卡预测——Smote+LR
  20. 使用HttpClient对ASP.NET Web API服务实现增删改查

热门文章

  1. Python之路【第十六篇】:Python并发编程|进程、线程
  2. STVD生成hex,bin,显示ram&amp;flash的使用情况
  3. 【leetcode-11】盛最多水的容器
  4. Linux 服务器 关闭FTP匿名访问
  5. spring Boot 学习(二、Spring Boot与缓存)
  6. python ocr中文识别库 tesseract安装及问题处理
  7. JQuey中ready()的4种写法
  8. TortoiseSVN安装和使用
  9. python关于try except的使用方法
  10. [LeetCode] 19. 删除链表的倒数第N个节点 ☆☆☆