生活随笔
收集整理的這篇文章主要介紹了
兰州大学第一届 飞马杯 ★★快乐苹果树★★ 树链剖分 + 懒标记 + 树状数组
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
傳送門(mén)
文章目錄
題意：
思路：
第一次聽(tīng)說(shuō)樹(shù)鏈剖分能在fa[top[i]]fa[top[i]]fa[top[i]]的地方加懶標(biāo)記，學(xué)到了學(xué)到了。
首先不能被題目嚇住，這個(gè)題目仔細(xì)剖析一下不難發(fā)現(xiàn)一些性質(zhì)：
以下用seise_isei?表示iii子樹(shù)的大小。
(1)(1)(1)當(dāng)uuu選擇了fff點(diǎn)，那么vvv選任一點(diǎn)都可以，也就是讓fff為根的子樹(shù)的每個(gè)點(diǎn)權(quán)值都加1sef1sefk\frac{1}{se_f}\frac{1}{se_f}ksef?1?sef?1?k。
(2)(2)(2)當(dāng)uuu選擇了非fff點(diǎn)的時(shí)候，其選擇的點(diǎn)假設(shè)落在與fff直接相連的xxx點(diǎn)所在的子樹(shù)中，那么vvv只能選非xxx的子樹(shù)中的點(diǎn)，也就是讓非xxx的子樹(shù)的點(diǎn)都加上sexsef1sef?sexk\frac{se_x}{se_f}\frac{1}{se_f-se_x}ksef?sex??sef??sex?1?k。
以上兩個(gè)操作顯然可以先將fff所在的子樹(shù)都加上1sef1sefk+∑sexsef1sef?sexk\frac{1}{se_f}\frac{1}{se_f}k+\sum \frac{se_x}{se_f}\frac{1}{se_f-se_x}ksef?1?sef?1?k+∑sef?sex??sef??sex?1?k，現(xiàn)在就有個(gè)比較顯然的做法就是遍歷fff的出邊給子樹(shù)減去sexsef1sef?sexk\frac{se_x}{se_f}\frac{1}{se_f-se_x}ksef?sex??sef??sex?1?k，fff的全部子樹(shù)都加上1sef1sefk+∑sexsef1sef?sexk\frac{1}{se_f}\frac{1}{se_f}k+\sum \frac{se_x}{se_f}\frac{1}{se_f-se_x}ksef?1?sef?1?k+∑sef?sex??sef??sex?1?k即可。
但這樣的話給你個(gè)菊花圖就炸了，復(fù)雜度升到qnlognqnlognqnlogn，由于是對(duì)子樹(shù)操作的，比較容易想到能不能加個(gè)懶標(biāo)記呢？我們加了懶標(biāo)記又如何在計(jì)算答案的時(shí)候能減去這個(gè)懶標(biāo)記呢？解決了這個(gè)兩個(gè)問(wèn)題我們就可以順利解決這個(gè)問(wèn)題了。
樹(shù)上倍增解決這個(gè)題不是很容易，我們考慮重鏈剖分。
首先我們加點(diǎn)的時(shí)候，思路就是按照上面哪個(gè)思路，即先給所有點(diǎn)都加上，再給子樹(shù)減去某個(gè)值，所以我們lazylazylazy標(biāo)記應(yīng)該是標(biāo)記了減去了多少。首先加操作顯然可以寫(xiě)一個(gè)dfsdfsdfs序，讓后用樹(shù)狀數(shù)組維護(hù)一下。考慮書(shū)剖的特殊性質(zhì)，我們只需要在tag[f]tag[f]tag[f]加上kkk，讓后將重兒子直接減去sexsef1sef?sexk\frac{se_x}{se_f}\frac{1}{se_f-se_x}ksef?sex??sef??sex?1?k，因?yàn)橹貎鹤釉谥筇?span id="ze8trgl8bvbq" class="katex--inline">toptoptop的時(shí)候會(huì)直接跳過(guò)的，而輕兒子在跳到這條鏈的top[i]top[i]top[i]的時(shí)候，需要減去s2[top[i]]?tag[fa[top[i]]]s2[top[i]]*tag[fa[top[i]]]s2[top[i]]?tag[fa[top[i]]]，s2s2s2是預(yù)處理的sexsef1sef?sex\frac{se_x}{se_f}\frac{1}{se_f-se_x}sef?sex??sef??sex?1?。
這樣問(wèn)題就順利解決啦~
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
#define lowbit(x) ((x)&(-x))
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=200010,mod
=998244353,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
,m
;
vector
<int>v
[N
];
int se
[N
],son
[N
],top
[N
],fa
[N
],in
[N
],tot
;
LL inv
[N
],s1
[N
],s2
[N
],s3
[N
];
LL tr
[N
],tag
[N
];void dfs1(int u
,int f
) {se
[u
]=1; fa
[u
]=f
;for(auto x
:v
[u
]) {if(x
==f
) continue;dfs1(x
,u
);se
[u
]+=se
[x
];if(se
[son
[u
]]<se
[x
]) son
[u
]=x
;}s1
[u
]=inv
[se
[u
]]*inv
[se
[u
]]%mod
;for(auto x
:v
[u
]) {if(x
==f
) continue;s2
[x
]=se
[x
]*inv
[se
[u
]]%mod
*inv
[se
[u
]-se
[x
]]%mod
;s3
[u
]+=s2
[x
]; s3
[u
]%=mod
;}
}void dfs2(int u
,int t
) {top
[u
]=t
; in
[u
]=++tot
;if(son
[u
]) dfs2(son
[u
],t
); for(auto x
:v
[u
]) {if(x
==fa
[u
]||x
==son
[u
]) continue;dfs2(x
,x
);}
}void add(int x
,LL c
) {for(int i
=x
;i
<=n
;i
+=lowbit(i
)) tr
[i
]+=c
,tr
[i
]%=mod
,tr
[i
]+=mod
,tr
[i
]%=mod
;
}LL
query(int x
) {LL ans
=0;for(int i
=x
;i
;i
-=lowbit(i
)) ans
+=tr
[i
],ans
%=mod
;return ans
;
}int main()
{
inv
[1]=1;for(int i
=2;i
<N
;i
++)inv
[i
]=(mod
-mod
/i
)*inv
[mod
%i
]%mod
;int _
; scanf("%d",&_
);while(_
--) {scanf("%d%d",&n
,&m
); tot
=0;for(int i
=1;i
<=n
;i
++) se
[i
]=son
[i
]=top
[i
]=fa
[i
]=s3
[i
]=s2
[i
]=s1
[i
]=0,v
[i
].clear();for(int i
=1;i
<=n
-1;i
++) {int a
,b
; scanf("%d%d",&a
,&b
);v
[a
].pb(b
); v
[b
].pb(a
);}dfs1(1,0); dfs2(1,1);while(m
--) {int op
,x
; scanf("%d%d",&op
,&x
);if(op
==1) {int k
; scanf("%d",&k
);add(in
[x
],1ll*(s1
[x
]+s3
[x
])%mod
*k
%mod
); add(in
[x
]+se
[x
],(((mod
-s1
[x
]-s3
[x
])%mod
+mod
)%mod
)*k
%mod
);if(son
[x
]) add(in
[son
[x
]],(mod
-s2
[son
[x
]]*k
%mod
)%mod
),add(in
[son
[x
]]+se
[son
[x
]],s2
[son
[x
]]*k
%mod
);tag
[x
]+=k
; tag
[x
]%=mod
;} else {LL ans
=query(in
[x
]);for(int i
=top
[x
];fa
[i
];i
=top
[fa
[i
]]) {ans
-=tag
[fa
[i
]]*s2
[i
]%mod
,ans
+=mod
,ans
%=mod
;}printf("%lld\n",ans
%mod
);}}for(int i
=1;i
<=n
;i
++) tr
[i
]=tag
[i
]=0;}return 0;
}
創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)
總結(jié)
以上是生活随笔為你收集整理的兰州大学第一届 飞马杯 ★★快乐苹果树★★ 树链剖分 + 懒标记 + 树状数组的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
