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 国的所有边都是无向边, 没有一条道路连接相同的一个城市
输入输出格式
输入格式:
输入第 1 行, 一个整数 \(N\)
输入第 2 至第 \(N\) 行, 每行三个正整数 \(u, v, w\), 表示城市 \(u\) 与城市 \(v\) 有一条值为 \(w\) 道路
输入第 \(N+1\) 行, 一个整数 \(M\), 表示 H 国有 \(M\) 条正在变化的道路
输入第 \(N+2\) 行到第 \(N+M+1\) 行, 每行 5 个整数 \(u, v, w, l, r\), 表示城市 \(u\) 到城市 \(v\) 有一条值为 \(w\) 的道路, 这条道路存在于第 \(l\) 天到第 \(r\) 天
输出格式:
输出共 32766 行, 第 \(i\) 行表示第 \(i\) 天游览的 \(L\) 值至少为多少
说明
对于所有数据 : \(1\leq N\leq 50000, 1\leq l\leq r\leq rm\leq 32766, 1\leq w\leq 10^9\)
线段树分治 + LCT 维护动态最小生成树, 比较裸
注意撤回的时候倒过来撤回, RE 了一次
- Code:
- #include <cstdio>
- #include <algorithm>
- #include <vector>
- #define ll long long
- #define fa par[now]
- #define ls ch[now][0]
- #define rs ch[now][1]
- using std::max;
- const int N=2e5+10;
- const int M=32766;
- int ch[N][2],par[N],tag[N],s[N],tot,tmp,n,m;ll sum;
- struct node
- {
- int mx,id;
- bool friend operator <(node n1,node n2){return n1.mx<n2.mx;}
- }dat[N],mx[N];
- bool isroot(int now){return ch[fa][0]==now||ch[fa][1]==now;}
- int identity(int now){return ch[fa][1]==now;}
- void updata(int now){mx[now]=max(dat[now],max(mx[ls],mx[rs]));}
- void connect(int f,int now,int typ){ch[fa=f][typ]=now;}
- void Reverse(int now){tag[now]^=1,tmp=ls,ls=rs,rs=tmp;}
- void pushdown(int now)
- {
- if(tag[now])
- {
- if(ls) Reverse(ls);
- if(rs) Reverse(rs);
- tag[now]^=1;
- }
- }
- void Rotate(int now)
- {
- int p=fa,typ=identity(now);
- connect(p,ch[now][typ^1],typ);
- if(isroot(p)) connect(par[p],now,identity(p));
- else fa=par[p];
- connect(now,p,typ^1);
- updata(p),updata(now);
- }
- void splay(int now)
- {
- while(isroot(now)) s[++tot]=now,now=fa;s[++tot]=now;
- while(tot) pushdown(s[tot--]);now=s[1];
- for(;isroot(now);Rotate(now))
- if(isroot(fa))
- Rotate(identity(now)^identity(fa)?now:fa);
- }
- void access(int now)
- {
- for(int las=0;now;las=now,now=fa)
- splay(now),rs=las,updata(now);
- }
- void evert(int now){access(now),splay(now),Reverse(now);}
- void split(int u,int v){evert(u),access(v),splay(v);}
- void link(int u,int v){evert(u),par[u]=v;}
- void cat(int u,int v){split(u,v),ch[v][0]=par[u]=0,updata(v);}
- node query(int u,int v){split(u,v);return mx[v];}
- std::vector <int> seg[N];
- void Insert(int id,int L,int R,int l,int r,int p)
- {
- if(L==l&&R==r) {seg[id].push_back(p);return;}
- int Mid=L+R>>1;
- if(r<=Mid) Insert(id<<1,L,Mid,l,r,p);
- else if(l>Mid) Insert(id<<1|1,Mid+1,R,l,r,p);
- else Insert(id<<1,L,Mid,l,Mid,p),Insert(id<<1|1,Mid+1,R,Mid+1,r,p);
- }
- struct edge{int u,v,w;}Edge[N];
- void segdivide(int id,int l,int r)
- {
- std::vector <int> sav;
- for(int i=0;i<seg[id].size();i++)
- {
- int p=seg[id][i],las=0;
- int u=Edge[p].u,v=Edge[p].v,w=Edge[p].w;
- node tmp=query(u,v);
- if(tmp.mx>w)
- {
- sum=sum+w-tmp.mx;
- las=tmp.id;
- cat(Edge[las].u,las+n),cat(Edge[las].v,las+n);
- link(u,p+n),link(v,p+n);
- }
- sav.push_back(las);
- }
- int mid=l+r>>1;
- if(l==r)
- printf("%lld\n",sum+1);
- else segdivide(id<<1,l,mid),segdivide(id<<1|1,mid+1,r);
- for(int las,p,i=seg[id].size()-1;~i;i--)
- {
- p=seg[id][i];
- if(las=sav[i])
- {
- int u=Edge[p].u,v=Edge[p].v;
- cat(u,p+n),cat(v,p+n);
- sum=sum+Edge[las].w-Edge[p].w;
- u=Edge[las].u,v=Edge[las].v;
- link(u,las+n),link(v,las+n);
- }
- }
- }
- int main()
- {
- scanf("%d",&n);
- for(int u,v,w,i=1;i<n;i++)
- {
- scanf("%d%d%d",&u,&v,&w);
- sum=sum+w;
- dat[i+n]=mx[i+n]={w,i};
- link(u,i+n),link(v,i+n);
- Edge[i]={u,v,w};
- }
- scanf("%d",&m);
- for(int u,v,w,l,r,i=0;i<m;i++)
- {
- scanf("%d%d%d%d%d",&u,&v,&w,&l,&r);
- Edge[i+n]={u,v,w};
- dat[i+(n<<1)]=mx[i+(n<<1)]={w,i+n};
- Insert(1,1,M,l,r,i+n);
- }
- segdivide(1,1,M);
- return 0;
- }
- 2018.12.8
来源: http://www.bubuko.com/infodetail-2877205.html