[NOIP10.6模拟赛]2.equation题解--树+线段树

题目链接:

咕

闲扯:

终于在集训中敲出正解(虽然与正解不完全相同),开心QAQ

首先比较巧,这题是$Ebola$出的一场模拟赛的一道题的树上强化版,当时还口胡出了那题的题解

然而考场上只得了86最后一个substask被卡了,一开始以为毒瘤出题人卡常(虽然真卡了)卡线段树,题目时限1.5s,评测机上两个点擦线1500ms左右,剩下两个点不知道。然后本地测一下都是1900+ms!机子性能已经这样了吗….结果把快读换成$fread$,TM过了!最慢的1200+ms!!!这……无话可说,$getchar()$快读也卡讲究

分析:

首先最简单的处理不讲了.就是把每个点的未知数表示成$k_i x_1 + b_i$的形式,这DFS一遍就好了

然后观察到有一个1e3的子任务,想想暴力怎么做,我们对于操作1,相当于$(k_i+k_j)x_1+(b_i+b_j)=w$判断一下解得情况就好了,$O(1)$完成;

对于操作2,我们可以发现对于$x$的操作,只会对$x$的子树中的$k_ix_1+b_i$形式有影响(实际上只会影响$b_i$),于是$DFS$一遍子树即可,这样总的暴力时间复杂度是$O(nq)$

考虑优化暴力,

我们发现瓶颈是操作2,如果将$x$与其父亲的边权从$w_1$改为$w_2$,那么加入$x$本来形式是$k_ix_1+b_i$,这时候变成了$k_i x_1+b_i+w_2-w_1$,相当于加操作,当时在$x$的子树中与$x$的$k_i$(实际上显然只有-1,1两种取值)不同的点,$b$值却应该减去$w_2-w_1$,所以我们将标记开成一个二元组,一个记录标记的正负,另一个记录值,重载下运算符就很方便了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct Tag{
        int o;//标记的正负
        ll dt;
        Tag(){o=dt=0;}
        Tag(int o){o=dt=o;}
        Tag(int _o,ll _dt){o=_o,dt=_dt;}
        Tag operator +(const Tag &b)const{
            Tag tmp=*this;
            if(tmp.o==0)tmp=b;
            else if(b.o==0)return tmp;
            else {
            	if(o!=b.o){
               	 tmp.dt=dt-b.dt;
            	}
            	else tmp.dt=dt+b.dt;
            }
            return tmp; 
        }
    };

这样对于操作2,只用在子树加个标记就好了,因为dfs序是一段连续区间(我比较傻考场上是用树链剖分)使用线段树就好了

对于操作1,我们两次单点查询就好了,然后按暴力那样处理.

总的时间复杂度$O(q log N)$,常数稍大

当然标算std是将深度分奇偶考虑,然后树状数组维护差分标记,时间复杂度相同但是常数小的多

代码

这是考场代码换了快读,如果想看线段树部分直接跳到$niconicoi$那个$namespace$就好了

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
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>
#define ll long long 
#define ri register int 
using std::min;
using std::abs;
using std::max;
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=nc()))ne=c=='-';
    x=c-48;
    while(isdigit(c=nc()))x=(x<<3)+(x<<1)+c-48;
    x=ne?-x:x;return ;
}
const int maxn=100005;
const int inf=0x7fffffff;
const int N=1000005;
struct Edge{
    int ne,to;
    ll dis;
}edge[N<<1];
int h[N],num_edge=1;
inline void add_edge(int f,int to,int c){
    edge[++num_edge].ne=h[f];
    edge[num_edge].to=to;
    edge[num_edge].dis=c;
    h[f]=num_edge;
}
struct Wt{
    int ki;
    ll bi;
    Wt(){ki=bi=0;}
    Wt(int _k,ll _b){ki=_k,bi=_b;}
}pt[N];
int n,q;
int fafa[N],fa_id[N];
namespace wtf{
    void main(){
        /*orz*/
        return ;
    }
}
void pre_dfs(int now,int fa){
    int v;
    int x=pt[now].ki,y=pt[now].bi;
    for(ri i=h[now];i;i=edge[i].ne){
        v=edge[i].to;
        if(v==fa)continue;
        fafa[v]=now;
        fa_id[v]=i;
        pt[v]=Wt(-x,edge[i].dis-y);
        pre_dfs(v,now);
    }
    return;
}
namespace qwq{
    void main(){
        int op,x,y;ll dd;
        ll p=edge[2].dis;
        while(q--){
            read(op),read(x),read(y);
            if(op==1){
                read(dd);
                if(x!=y){
                    if(dd==p){
                        puts("inf");
                    }
                    else{
                        puts("none");
                    }
                }
                else {
                    if(x==1){
                        if(dd%2)puts("none");
                        else printf("%lld\n",dd/2);
                    }
                    if(x==2){
                        ll tt=2*p-dd;
                        if(tt%2)puts("none");
                        else printf("%lld\n",tt/2);
                    }
                }
            }
            else{
                p=y;
            }
        }
        return ;
    }
}
namespace task_1{
    void main(){
        int op,x,y;ll dd;
        int kk,bb;
        while(q--){
            read(op),read(x),read(y);
            if(op==1){
                read(dd);
                kk=pt[x].ki+pt[y].ki;
                bb=pt[x].bi+pt[y].bi;
                dd=dd-bb;
                if(kk==0){
                    if(dd==0)puts("inf");
                    else puts("none");
                }
                else if(dd%abs(kk)!=0)puts("none");
                else printf("%lld\n",dd/kk);
            }
            else {
                edge[fa_id[x]].dis=y;
                edge[fa_id[x]^1].dis=y;
                pre_dfs(fafa[x],fafa[fafa[x]]);
            }
        }
        return ;
    }
}
namespace niconiconi{
    int dep[N],top[N],son[N],size[N],dfn[N],rnk[N],tot=0;
    void print(ll xxx){
        if(!xxx)return ;
		print(xxx/10);
        putchar(xxx%10+'0');   
        return ;
    }
    void dfs_1(int now){
        int v;size[now]=1;
        for(ri i=h[now];i;i=edge[i].ne){
            v=edge[i].to;
            if(v==fafa[now])continue;
            dep[v]=dep[now]+1;
            dfs_1(v);
            size[now]+=size[v];
            if(!son[now]||size[son[now]]<size[v])son[now]=v;
        }
        return ;
    }
    void dfs_2(int now,int t){
        int v;top[now]=t;
        dfn[now]=++tot,rnk[tot]=now;
        if(!son[now])return ;
        dfs_2(son[now],t);
        for(ri i=h[now];i;i=edge[i].ne){
            v=edge[i].to;
            if(v==fafa[now]||v==son[now])continue;
            dfs_2(v,v);
        }
        return ;
    }
    struct Tag{
        int o;//标记的正负
        ll dt;
        Tag(){o=dt=0;}
        Tag(int o){o=dt=o;}
        Tag(int _o,ll _dt){o=_o,dt=_dt;}
        Tag operator +(const Tag &b)const{
            Tag tmp=*this;
            if(tmp.o==0)tmp=b;
            else if(b.o==0)return tmp;
            else {
            	if(o!=b.o){
               	 tmp.dt=dt-b.dt;
            	}
            	else tmp.dt=dt+b.dt;
            }
            return tmp; 
        }
    };
	Tag tag[N<<2];
    void build(int now,int l,int r){
        tag[now]=Tag(0);
        if(l==r){
            return ;
        }
        int mid=(l+r)>>1;
        build(now<<1,l,mid);
        build(now<<1|1,mid+1,r);
        return ;
    }
    int L,R;
    Tag dta;
    inline void pushdown(int now){
        if(tag[now].o==0)return ;
        tag[now<<1]=tag[now<<1]+tag[now];
        tag[now<<1|1]=tag[now<<1|1]+tag[now];
        tag[now]=Tag(0);
        return ;
    }
    void update(int now,int l,int r){
        if(L<=l&&r<=R){
            tag[now]=tag[now]+dta;
            return ;
        }
        int mid=(l+r)>>1;
        pushdown(now);
        if(L<=mid)update(now<<1,l,mid);
        if(mid<R)update(now<<1|1,mid+1,r);
        return ;
    }
    Wt pa,pb;
	int t;
    void query(int now,int l,int r){
        if(l==r){
            //int kkk=pt[rnk[l]].ki,bbb=pt[rnk[l]].bi;
            if(tag[now].o!=0){
                if(tag[now].o!=pt[rnk[l]].ki){
                    pt[rnk[l]].bi-=tag[now].dt;
                }
                else{
                    pt[rnk[l]].bi+=tag[now].dt;
                }
                tag[now]=Tag(0);
            }
            //pa.ki=pt[rnk[l]].ki;
            //pa.bi=pt[rnk[l]].bi;
            return;
        }
        int mid=(l+r)>>1;
        pushdown(now);
        if(t<=mid)query(now<<1,l,mid);
        else query(now<<1|1,mid+1,r);
        return ;
    }
    void main(){
        int op,x,y;
        ll kk,bb,dd;
        dep[1]=0;
        dfs_1(1);
        dfs_2(1,1);
        build(1,1,n);
        while(q--){
            read(op),read(x),read(y);
            if(op==1){
                read(dd);
                t=dfn[x];//pa=Wt(0,0);
                query(1,1,n);
                t=dfn[y];//pb=Wt(pa.ki,pa.bi),pa=Wt(0,0);
                query(1,1,n);
                //printf("%d %d %d %d\n",pa.ki,pb.ki,pa.bi,pb.bi);
                kk=pt[x].ki+pt[y].ki;
                bb=pt[x].bi+pt[y].bi;
                dd=dd-bb;
                if(kk==0){
                    if(dd==0)puts("inf");
                    else puts("none");
                }
                else if(dd%abs(kk)!=0)puts("none");
                else {
                    if(dd==0)puts("0");
                    else {
                    	dd=dd/kk;
                    	if(dd<0)dd=-dd,putchar('-');
						print(dd);
						puts("");
					}
                    //printf("%lld\n",dd/kk);
                }
            }
            else {
                dd=edge[fa_id[x]].dis;
                edge[fa_id[x]].dis=edge[fa_id[x]^1].dis=y;
                dd=1ll*y-dd;
                //printf("%lld\n",dd);
                L=dfn[x],R=dfn[x]+size[x]-1;
                //t=dfn[x];pa=Wt(0,0);
                //query(1,1,n);
                pa=pt[x];
                //printf("%d\n",pa.ki);
                dta=Tag(pa.ki,dd);
                update(1,1,n);
                //update_subtree()
            }
        }
        return ;
    }
}
int main(){
    int x,y;
    freopen("equation.in","r",stdin);
    freopen("equation.out","w",stdout);
    read(n),read(q);
    for(ri i=2;i<=n;i++){
        read(x),read(y);
        add_edge(i,x,y);
        add_edge(x,i,y);
    }
    pt[1].ki=1,pt[1].bi=0;
    fafa[1]=0;
    pre_dfs(1,0);
    if(q==0)wtf::main();
    else if(n==2)qwq::main();
    else if(n<=2000)task_1::main();
    else niconiconi::main();
    fclose(stdin);
    fclose(stdout);
    return 0;
}