[비조이 2018] 화합하기.
8934 단어 제목 분석나무의 갈라진 부분세그먼트 트리
제목 설명:
∑x∈Path(u, v)deep(x)k ∑x∈P a t h(u, v)d e ep(x)k
제목 분석:
K가 비교적 작은 나무 단면과 배가되어 유지보수가 가능하다는 것을 알아차리다.
제목 링크:
BZOJ 5293 Luogu 4427
Ac 코드:
나무가 쪼개지는 게 느려..
#include
#include
#include
#include
#include
const int maxm=310000;
const int mod=998244353;
int sum[maxm*4][51];
int head[maxm],to[maxm<<1],net[maxm<<1],cnt;
int deep[maxm],fa[maxm],siz[maxm],id[maxm],rank[maxm],top[maxm],son[maxm],tot;
int n,m,k;
struct node{
int u,v,kth;
}q[maxm];
inline void addedge(int u,int v)
{
cnt++;
to[cnt]=v,net[cnt]=head[u],head[u]=cnt;
}
inline int read()
{
int x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return x*w;
}
void dfs1(int now)
{
siz[now]=1;
for(int i=head[now];i;i=net[i])
if(to[i]!=fa[now])
{
deep[to[i]]=deep[now]+1;
fa[to[i]]=now;
dfs1(to[i]);
siz[now]+=siz[to[i]];
if(siz[son[now]]int now,int topx)
{
rank[id[now]=++tot]=now;
top[now]=topx;
if(son[now]) dfs2(son[now],topx);
for(int i=head[now];i;i=net[i])
if(!id[to[i]]) dfs2(to[i],to[i]);
}
inline void add(int &x,int y)
{
x+=y;
if(x>=mod) x%=mod;
}
void build(int o,int l,int r)
{
if(l>=r)
{
//printf("%d %d %d
",l,rank[l],deep[rank[l]]);
sum[o][0]=1;
for(int i=1;i<=k;i++)
add(sum[o][i],(int)((1ll*sum[o][i-1]*deep[rank[l]])%mod));
return;
}
int mid=(l+r)>>1;
build((o<<1),l,mid),build((o<<1)|1,mid+1,r);
for(int i=1;i<=k;i++)
{
add(sum[o][i],sum[(o<<1)][i]);
add(sum[o][i],sum[(o<<1)|1][i]);
}
}
int ask(int o,int l,int r,int ql,int qr,int kth)
{
if(ql<=l&&r<=qr) return sum[o][kth];
int mid=(l+r)>>1;
int ans=0;
if(ql<=mid) add(ans,ask((o<<1),l,mid,ql,qr,kth));
if(qr>mid) add(ans,ask((o<<1)|1,mid+1,r,ql,qr,kth));
return ans;
}
inline int treesum(int u,int v,int kth)
{
int ans=0;
while(top[u]!=top[v])
{
if(deep[top[u]]1,1,n,id[top[u]],id[u],kth));
u=fa[top[u]];
}
if(deep[u]1,1,n,id[v],id[u],kth));
return ans;
}
int main()
{
n=read();
for(int i=1;iint u,v;
u=read(),v=read();
addedge(u,v),addedge(v,u);
}
dfs1(1),dfs2(1,1);
m=read();
for(int i=1;i<=m;i++)
q[i].u=read(),q[i].v=read(),q[i].kth=read(),k=std::max(q[i].kth,k);
build(1,1,n);
for(int i=1;i<=m;i++)
printf("%d
",treesum(q[i].u,q[i].v,q[i].kth));
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
YY의 GCD∑ni=1∑mj=1(gcd(i,j)==pi)∑i=1n∑j=1m(gcd(i,j)==pi)pi는 질수 pi는 질수 프리 프로세싱μ(Tp) μ (T p) 접두사 및 Luogu 2257...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.