[동적 트 리 분할] [bzoj 4012]: [HNOI 2015] 오픈
3372 단어 코드
한눈 에 보 는 우리 문제...
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define rep(i,l,r) for(int i=(l),_=(r);i<=_;i++)
#define per(i,r,l) for(int i=(r),_=(l);i>=_;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define INE(i,u) for(int i=head[u];~i;i=e[i].next)
#define LL long long
#define X first
#define Y second
typedef pairpil;
inline const int read()
{int r=0,k=1;char c=getchar();for(;c'9';c=getchar())if(c=='-')k=-1;
for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';return k*r;}
inline void MAX(int &a,int b){if(adis; // (age,dis)
vectordisf; // (age,dis)
}T[N];
int dis[N],dep[N],fa[N][17];
void adde(int u,int v,int w){e[k]=(edge){v,w,head[u]};head[u]=k++;}
void dfs2(int u)
{
INE(i,u)
{
int v=e[i].v; if(v==fa[u][0]) continue;
fa[v][0]=u; rep(i,1,16) fa[v][i]=fa[fa[v][i-1]][i-1];
dep[v]=dep[u]+1; dis[v]=dis[u]+e[i].w;
dfs2(v);
}
}
int lca(int x,int y)
{
if(dep[x]>i&1) x=fa[x][i];
if(x==y) return x;
per(i,16,0) if(fa[x][i]^fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int getdis(int x,int y)
{
return dis[x]+dis[y]-2*dis[lca(x,y)];
}
void getroot(int u,int fa)
{
cnt[u]=1; mx[u]=0;
INE(i,u)
{
int v=e[i].v; if(v==fa || flag[v]) continue;
getroot(v,u);
cnt[u]+=cnt[v];
MAX(mx[u],cnt[v]);
}
MAX(mx[u],size-cnt[u]);
if(mx[u]R) return pil(0,0);
if(L) return pil(R-L+1,T[rt].dis[R].Y-T[rt].dis[L-1].Y);
else return pil(R-L+1,T[rt].dis[R].Y);
}
pil getdissumf(int rt,int l,int r) // (cnt,dissum)
{
int L=lower_bound(T[rt].disf.begin(),T[rt].disf.end(),pil(l,0))-T[rt].disf.begin();
int R=lower_bound(T[rt].disf.begin(),T[rt].disf.end(),pil(r+1,0))-T[rt].disf.begin();
R--;
if(L>R) return pil(0,0);
if(L) return pil(R-L+1,T[rt].disf[R].Y-T[rt].disf[L-1].Y);
else return pil(R-L+1,T[rt].disf[R].Y);
}
LL getans(int rt,int u,int l,int r)
{
int f=T[rt].fa;
LL res=0;
if(u==rt)
{
res+=getdissum(rt,l,r).Y;
}
if(f==0) return res;
pil retf=getdissum(f,l,r);
pil retr=getdissumf(rt,l,r);
res+=retf.Y-retr.Y;
res+=(LL)(retf.X-retr.X)*getdis(f,u);
return res+getans(f,u,l,r);
}
void input()
{
MS(head,-1);
n=read(); q=read(); A=read();
rep(i,1,n) w[i]=read();
rep(i,2,n)
{
int u=read(),v=read(),w=read();
adde(u,v,w); adde(v,u,w);
}
}
void solve()
{
dfs2(1);
size=mx[rt=0]=n;
getroot(1,0);
divide(rt);
LL lstans=0;
while(q--)
{
//lstans=0;
int u=read(),a=read(),b=read(),l,r;
l=(a+lstans)%A; r=(b+lstans)%A;
if(l>r) swap(l,r);
printf("%lld
",lstans=getans(u,u,l,r));
}
}
int main()
{
freopen("_.in","r",stdin); freopen("A.out","w",stdout);
input(),solve();
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
vue 단일 페이지에 여러 개의 echarts 도표가 있을 때의 공용 코드 쓰기html에서: 데이터 처리는 말할 필요가 없다.응, 직접 그림을 그려: 공통 섹션: 이 페이지를 떠날 때 파괴: 추가 정보: Vue + Echarts 차트 표시 및 동적 렌더링 준비 작업 echarts 의존 설치 n...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.