傳送門

題意:給一棵帶點(diǎn)權(quán)的有根樹，求所有滿足$u$是$v$的祖先的路徑$(u,v)$的路徑上所有點(diǎn)權(quán)的$gcd$的和模$1e9+7$。

$N\le 100000$

看到連續(xù)$gcd$多半是根據(jù)單調(diào)性維護(hù)鏈表之類的

對于每個點(diǎn)，記錄所有祖先到它的路徑$gcd$

由于最多只有$O(logV)$種取值并且是單調(diào)變倍數(shù)的，所以每一段只用維護(hù)開始位置和$gcd$

到子節(jié)點(diǎn)時相當(dāng)于父節(jié)點(diǎn)的所有數(shù)與子節(jié)點(diǎn)的權(quán)值取$gcd$再加上自己

那么之前的一段仍是一段，并且有些段會合并

由于是$log$級別的，所以直接開$N$個$vector$,用父節(jié)點(diǎn)的暴力更新

復(fù)雜度$O(n{\log }^{2}V)$

略精神污染

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <vector> #include <utility> #define MAXN 100005 #define MAXM 200005 using namespace std; const int MOD=1e9+7; typedef long long ll; typedef pair<int,ll> pi; ll gcd(ll a,ll b){return b? gcd(b,a%b):a;} int ans=0; struct edge{int u,v;}e[MAXM]; int head[MAXN],nxt[MAXM],cnt; void addnode(int u,int v) {e[++cnt]=(edge){u,v};nxt[cnt]=head[u];head[u]=cnt; } vector<pi> lis[MAXN]; int dep[MAXN],fa[MAXN]; ll x[MAXN]; void dfs(int u) { // int b=ans;if (fa[u]) lis[u].push_back(make_pair(lis[fa[u]][0].first,gcd(x[u],lis[fa[u]][0].second)));for (int i=1;i<lis[fa[u]].size();i++){ll t=gcd(x[u],lis[fa[u]][i].second);if (t==lis[u].back().second) continue;ans=(ans+lis[u].back().second*(dep[lis[fa[u]][i].first]-dep[lis[u].back().first])%MOD)%MOD;lis[u].push_back(make_pair(lis[fa[u]][i].first,t));}if (lis[u].empty()) lis[u].push_back(make_pair(u,x[u])),ans=(ans+x[u])%MOD;elseif (lis[u].back().second!=x[u]) ans=(ans+lis[u].back().second*(dep[u]-dep[lis[u].back().first])%MOD)%MOD,lis[u].push_back(make_pair(u,x[u])),ans=(ans+x[u])%MOD;else ans=(ans+x[u]*(dep[u]-dep[lis[u].back().first]+1)%MOD)%MOD; // printf("%d:\n",u); // for (int i=0;i<lis[u].size();i++) printf("%d %lld\n",lis[u][i].first,lis[u][i].second); // printf("contribution:%d\n",ans-b);for (int i=head[u];i;i=nxt[i])if (!dep[e[i].v]){dep[e[i].v]=dep[u]+1;fa[e[i].v]=u;dfs(e[i].v);} } int main() {int n;scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%I64d",&x[i]);for (int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);addnode(u,v);addnode(v,u);}dep[1]=1;dfs(1);cout<<ans;return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的【CF1230E】Kamil and Making a Stream【GCD性质】【暴力vector】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。