青岛网站关键词,wordpress 多条件过滤,外贸网站自建站,株洲网站建设推广报价传送门
题意:给一棵带点权的有根树#xff0c;求所有满足uuu是vvv的祖先的路径(u,v)(u,v)(u,v)的路径上所有点权的gcdgcdgcd的和模1e971e971e97。 N≤100000N \leq 100000N≤100000
看到连续gcdgcdgcd多半是根据单调性维护链表之类的
对于每个点#xff0c;记录所有祖先到…传送门
题意:给一棵带点权的有根树求所有满足uuu是vvv的祖先的路径(u,v)(u,v)(u,v)的路径上所有点权的gcdgcdgcd的和模1e971e971e97。
N≤100000N \leq 100000N≤100000
看到连续gcdgcdgcd多半是根据单调性维护链表之类的
对于每个点记录所有祖先到它的路径gcdgcdgcd
由于最多只有O(logV)O(logV)O(logV)种取值并且是单调变倍数的所以每一段只用维护开始位置和gcdgcdgcd
到子节点时相当于父节点的所有数与子节点的权值取gcdgcdgcd再加上自己
那么之前的一段仍是一段并且有些段会合并
由于是logloglog级别的所以直接开NNN个vectorvectorvector,用父节点的暴力更新
复杂度O(nlog2V)O(n\log ^2V)O(nlog2V)
略精神污染
#include iostream
#include cstdio
#include cstring
#include cctype
#include vector
#include utility
#define MAXN 100005
#define MAXM 200005
using namespace std;
const int MOD1e97;
typedef long long ll;
typedef pairint,ll pi;
ll gcd(ll a,ll b){return b? gcd(b,a%b):a;}
int ans0;
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;
}
vectorpi lis[MAXN];
int dep[MAXN],fa[MAXN];
ll x[MAXN];
void dfs(int u)
{
// int bans;if (fa[u]) lis[u].push_back(make_pair(lis[fa[u]][0].first,gcd(x[u],lis[fa[u]][0].second)));for (int i1;ilis[fa[u]].size();i){ll tgcd(x[u],lis[fa[u]][i].second);if (tlis[u].back().second) continue;ans(anslis[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(ansx[u])%MOD;elseif (lis[u].back().second!x[u]) ans(anslis[u].back().second*(dep[u]-dep[lis[u].back().first])%MOD)%MOD,lis[u].push_back(make_pair(u,x[u])),ans(ansx[u])%MOD;else ans(ansx[u]*(dep[u]-dep[lis[u].back().first]1)%MOD)%MOD;
// printf(%d:\n,u);
// for (int i0;ilis[u].size();i) printf(%d %lld\n,lis[u][i].first,lis[u][i].second);
// printf(contribution:%d\n,ans-b);for (int ihead[u];i;inxt[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 i1;in;i) scanf(%I64d,x[i]);for (int i1;in;i){int u,v;scanf(%d%d,u,v);addnode(u,v);addnode(v,u);}dep[1]1;dfs(1);coutans;return 0;
}