【CF838-B】Diverging Directions

Source and Judge

CF838-B

Problem

【Description】
西瓜们生活在编号 1⋯n 的 n个平行时空中,2n−2 台时光机将这些平行时空联系在一起。
一台时光机有 3个整数参数 u,v,t 表示从时空 u 可以花费 t 的时间穿梭到时空 v。
为了确保时空之间可以相互穿梭,同时方便作为现世的 1号时空的通行,西瓜们将这些时光机进行分工:前 n−1 台时光机确保从 1号时空可以直接 / 间接抵达任意时空,后 n−1台时光机负责从 2⋯n号时空直接返回 1号时空。
【Input】
第一行 3 个整数 n,q 分别表示 平行时空,操作 的个数。
接下来 2n−2 行,每行 3 个整数 u,v,t 表示一台时光机。
接下来 q 行,每行 3 个整数 id,x,y:
若 $id=1$,表示第 $x$ 台时光机的运行时间变成了 $y$。
若 $id=2$,表示当前有一个西瓜想要从时空 $x$ 穿梭到 时空 $y$;
【Output】
每次询问输出最短时间。
【Limited conditions】
n,q<=2*10^6
【Sample input】
5 9
1 3 1
3 2 2
1 4 3
3 5 4
5 1 5
3 1 6
2 1 7
4 1 8
2 1 1
2 1 3
2 3 5
2 5 2
1 1 100
2 1 3
1 8 30
2 4 2
2 2 4
【Sample output】
0
1
4
8
100
132
10
【Sample explanation】

Record

1h

Analysis

请先思考

显然是一个树
类似树链剖分的思想,准确地说是dfs序
如果对dfs序不是很懂的话,可以去看看这道经典题软件包管理器
很水呀但是机房居然只有三个人过……

Code

请先思考
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<cstdio>
#include<cstring>
#include<algorithm>
const int INF=0x3f3f3f3f;
typedef long long ll;
void qread(int &x)
{
x=0;char c=getchar();
while(c<'0' or c>'9') c=getchar();
while(c>='0' and c<='9') x=x*10+c-'0',c=getchar();
}
void qreadll(ll &x)
{
x=0;char c=getchar();
while(c<'0' or c>'9') c=getchar();
while(c>='0' and c<='9') x=x*10ll+c-'0',c=getchar();
}
ll mymin(ll x,ll y) {return (x<y)?x:y;}
const int MAXN=210000;
struct Seg
{
int l,r,mid;
int lc,rc;
ll mi,lz;
}s[MAXN*2];
int cnt=0;
int build(int l,int r)
{
int t=++cnt;
if(l==r) s[t]=(Seg){l,r,l,0,0,0,0};
else
{
s[t]=(Seg){l,r,(l+r)>>1,0,0,0,0};
s[t].lc=build(l,s[t].mid);
s[t].rc=build(s[t].mid+1,r);
s[t].mi=mymin(s[s[t].lc].mi,s[s[t].rc].mi);
}
return t;
}
void pushdown(int x)
{
int lc=s[x].lc,rc=s[x].rc;
if(lc>0) {s[lc].mi+=s[x].lz;s[lc].lz+=s[x].lz;}
if(rc>0) {s[rc].mi+=s[x].lz;s[rc].lz+=s[x].lz;}
s[x].lz=0;
}
void change(int x,int l,int r,ll o)
{
if(s[x].l==l and s[x].r==r)
{
s[x].mi+=o;
s[x].lz+=o;
return;
}
if(s[x].lz!=0) pushdown(x);
int lc=s[x].lc,rc=s[x].rc;
if(r<=s[x].mid) change(lc,l,r,o);
else if(l>s[x].mid) change(rc,l,r,o);
else change(lc,l,s[x].mid,o),change(rc,s[x].mid+1,r,o);
s[x].mi=mymin(s[lc].mi,s[rc].mi);
}
ll ask(int x,int l,int r)
{
if(s[x].l==l and s[x].r==r) return s[x].mi;
if(s[x].lz!=0) pushdown(x);
int lc=s[x].lc,rc=s[x].rc;
if(r<=s[x].mid) return ask(lc,l,r);
if(l>s[x].mid) return ask(rc,l,r);
return mymin( ask(lc,l,s[x].mid),ask(rc,s[x].mid+1,r) );
}
struct Nod
{
int hou;
int siz;
ll dis,tt;
Nod()
{
hou=0;
}
}p[MAXN];
struct Edge
{
int y,g;ll c;
}e[MAXN*2];
int ln=0;
void ins(int x,int y,ll c)
{
e[++ln]=(Edge){y,p[x].hou,c};p[x].hou=ln;
}
int yz[MAXN],id=0;
void dfs(int x,int fa)
{
yz[x]=++id;p[x].siz=1;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
p[y].dis=p[x].dis+e[k].c;
dfs(y,x);
p[x].siz+=p[y].siz;
}
}
struct SG
{
int x,y;
ll z;
}ss[2*MAXN];
ll solve(int x,int y)
{
if(yz[x]<=yz[y] and yz[y]<=yz[x]+p[x].siz-1)
return ( ask(1,yz[y],yz[y])-p[y].tt )-( ask(1,yz[x],yz[x])-p[x].tt );
return ask(1,yz[x],yz[x]+p[x].siz-1)-(ask(1,yz[x],yz[x])-p[x].tt)+(ask(1,yz[y],yz[y])-p[y].tt);
}
int main()
{
int n,q;qread(n);qread(q);
for(int i=1;i<=2*n-2;i++)
{
int x,y;ll z;
qread(x);qread(y);qreadll(z);
ss[i]=(SG){x,y,z};
if(y==1) p[x].tt=z;
else ins(x,y,z);
}
dfs(1,0);
build(1,n);
for(int i=2;i<=n;i++) change(1,yz[i],yz[i],p[i].dis+p[i].tt);
while(q--)
{
int id,x,y;qread(id);qread(x);qread(y);
if(id==2) printf("%I64d\n",solve(x,y));
else
{
int nx=ss[x].x,ny=ss[x].y;
if(ny==1) change(1,yz[nx],yz[nx],-p[nx].tt+y),p[nx].tt=y;
else change(1,yz[ny],yz[ny]+p[ny].siz-1,-ss[x].z+y),ss[x].z=y;
}
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-04/Diverging_Directions.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%