wxwoo's blog

原题目链接

首先树剖边权转点权,把每一条边的权值下放到子节点上

在修改的时候注意最后要避开两个点的LCA,因为LCA的点权所代表的边权不在两个点的路径上

然后看见区间推平就想到了ODT

ODT比线段树短,好写,细节还比线段树少

但是不保证数据随机,ODT的时间复杂度没有保证

最后写出来跑了6s,被LCT和树剖+线段树吊打

代码如下

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#include<set>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x)
{
int ch=getchar();
T f=1;
x=0;
while(!('0'<=ch&&ch<='9'))
{
if(ch=='-')
f=-1;
ch=getchar();
}
while('0'<=ch&&ch<='9')
{
x=(x<<3)+(x<<1)+ch-48;
ch=getchar();
}
x*=f;
}
#define setit set<node>::iterator
const int N=100010;
struct node
{
int l,r;
mutable int val;
node(int L,int R=-1,int V=0):l(L),r(R),val(V){}
friend inline bool operator<(const node &a,const node &b)
{
return a.l<b.l;
}
};
set<node>s;
int n;
int u[N],v[N],head[N],nxt[N<<1],to[N<<1],val[N<<1],e;
inline void addedge(const int &u,const int &v,const int &w)
{
to[++e]=v;
val[e]=w;
nxt[e]=head[u];
head[u]=e;
}
int fa[N],son[N],dep[N],sz[N],w[N],top[N],id[N],seq[N],cnt;
char str[10];
inline setit split(const int &x)
{
setit it=s.lower_bound(node(x));
if(it!=s.end()&&it->l==x)
return it;
--it;
int l=it->l,r=it->r,val=it->val;
s.erase(it);
s.insert(node(l,x-1,val));
return s.insert(node(x,r,val)).first;
}
inline void assign(const int &l,const int &r,const int &k)
{
setit itr=split(r+1),itl=split(l);
s.erase(itl,itr);
s.insert(node(l,r,k));
}
inline void add(const int &l,const int &r,const int &k)
{
setit itr=split(r+1),itl=split(l);
for(;itl!=itr;++itl)
itl->val+=k;
}
inline int query(const int &l,const int &r)
{
int ans=0;
setit itr=split(r+1),itl=split(l);
for(;itl!=itr;++itl)
ans=max(ans,itl->val);
return ans;
}
void dfs1(const int &x,const int &f,const int &d)
{
fa[x]=f;
dep[x]=d;
sz[x]=1;
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==f)
continue;
dfs1(y,x,d+1);
w[y]=val[i];
sz[x]+=sz[y];
if(sz[y]>sz[son[x]])
son[x]=y;
}
}
void dfs2(const int &x,const int &t)
{
top[x]=t;
id[x]=++cnt;
seq[cnt]=x;
if(!son[x])
return;
dfs2(son[x],t);
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==son[x]||y==fa[x])
continue;
dfs2(y,y);
}
}
inline void addchain(int x,int y,const int &k)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
add(id[top[x]],id[x],k);
x=fa[top[x]];
}
if(x==y)
return;
if(dep[x]>dep[y])
swap(x,y);
add(id[x]+1,id[y],k);
}
inline void covchain(int x,int y,const int &k)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
assign(id[top[x]],id[x],k);
x=fa[top[x]];
}
if(x==y)
return;
if(dep[x]>dep[y])
swap(x,y);
assign(id[x]+1,id[y],k);
}
inline int maxchain(int x,int y)
{
int res=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
res=max(res,query(id[top[x]],id[x]));
x=fa[top[x]];
}
if(x==y)
return res;
if(dep[x]>dep[y])
swap(x,y);
return max(res,query(id[x]+1,id[y]));
}
inline void updedge(int u,int v,const int &k)
{
if(fa[v]==u)
swap(u,v);
assign(id[u],id[u],k);
}
int main()
{
read(n);
for(int i=1;i<n;++i)
{
int w;
read(u[i]);
read(v[i]);
read(w);
addedge(u[i],v[i],w);
addedge(v[i],u[i],w);
}
dfs1(1,1,1);
dfs2(1,1);
for(int i=2;i<=n;++i)
s.insert(node(i,i,w[seq[i]]));
int l,r,k;
while(1)
{
scanf("%s",str);
if(str[1]=='t')
break;
read(l);
read(r);
if(str[1]=='a')
printf("%d\n",maxchain(l,r));
else if(str[1]=='h')
updedge(u[l],v[l],r);
else
{
read(k);
if(str[1]=='o')
covchain(l,r,k);
else
addchain(l,r,k);
}
}
return 0;
}

原题目链接

树上链最值查询

做法很多,LCT,树上倍增,树剖都可以

但由于LCT常数过大,树上倍增比树剖常数大,这里使用树链剖分

边权转点权是树剖常用套路,将边权转成深度较大的点的点权,查询时注意避开两点的LCA的权值

由于不带修改,树剖后用ST表维护,时间复杂度$\mathcal{O}(n\log n)$,比用线段树维护$\mathcal{O}(n\log ^2n)$还少一个log

载入天数...载入时分秒...


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Material X 作为主题 , 总访问量为 次 。