bzoj 3626 LCA
여기에 코드 하나만 넣을게요.
이런 문제를 1A로 올리는 쾌감은 정말 빠져들게 한다.
(첫 번째 CE는 제외
#include<bits/stdc++.h>
using namespace std;
const int maxn = 52345;
const int mod = 201314;
const int ROOT = 0;
int n;
vector<int> edge[maxn];
void init(int n){
for(int i=0;i<=n;i++){
edge[i].clear();
}
}
void Link(int st,int ed){
edge[st].push_back(ed);
edge[ed].push_back(st);
}
int fa[maxn],son[maxn],siz[maxn],deep[maxn],top[maxn],tid[maxn];
int _cnt;
void dffs(int st,int Fa,int Deep){
siz[st] = 1,deep[st] = Deep;
fa[st] = Fa,son[st] = -1;
for(vector<int>::iterator it = edge[st].begin();it!=edge[st].end();it++){
int x = *it;
if(x != Fa){
dffs(x,st,Deep+1);
siz[st] += siz[x];
if(son[st] == -1 || siz[son[st]] < siz[x])
son[st] = x;
}
}
}
void dfss(int st,int Top){
top[st] = Top,tid[st] = _cnt++;
if(son[st] != -1)
dfss(son[st],Top);
for(vector<int>::iterator it = edge[st].begin();it!=edge[st].end();it++){
int x = *it;
if(son[st] != x && fa[st] != x){
dfss(x,x);
}
}
}
void splite(){
_cnt = 1;
dffs(ROOT,-1,0);
dfss(ROOT,ROOT);
}
#define root 1,1,n
#define lson o<<1,l,m
#define rson o<<1|1,m+1,r
#define Now int o,int l,int r
#define Mid int m = (l+r)>>1
int sec[maxn*4];
int lazy[maxn*4];
void sinit(){
memset(sec,0,sizeof(sec));
memset(lazy,0,sizeof(lazy));
}
void push_down(Now){
if(l == r){
lazy[o] = 0;
return;
}
int v = lazy[o];
lazy[o] = 0;
Mid;
(sec[o<<1] += (m-l+1) * v) %= mod;
(lazy[o<<1] += v)%= mod;
(sec[o<<1|1] += (r - (m+1) + 1) * v)%= mod;
(lazy[o<<1|1] += v)%= mod;
}
void update(Now,int ul,int ur){
if(ul <= l && r <= ur){
lazy[o]++;
sec[o] += (r - l + 1);
lazy[o] %= mod;
sec[o] %= mod;
return;
}
Mid;
if(lazy[o])
push_down(o,l,r);
if(ul <= m)
update(lson,ul,ur);
if(m+1 <= ur)
update(rson,ul,ur);
sec[o] = (sec[o<<1] + sec[o<<1|1]) % mod;
}
int query(Now,int ql,int qr){
if(ql <= l && r <= qr){
return sec[o];
}
Mid;
if(lazy[o])
push_down(o,l,r);
int ret = 0;
if(ql <= m)
ret += query(lson,ql,qr);
if(m+1 <= qr)
ret += query(rson,ql,qr);
return ret % mod;
}
void UPD(int x,int y){
int tx = top[x],ty = top[y];
while(tx != ty){
if(deep[tx]<deep[ty])
swap(tx,ty),swap(x,y);
update(root,tid[tx],tid[x]);
x = fa[tx],tx = top[x];
}
if(deep[x] < deep[y])
swap(x,y);
update(root,tid[y],tid[x]);
}
int QUE(int x,int y){
int ret = 0;
int tx = top[x],ty = top[y];
while(tx != ty){
if(deep[tx] < deep[ty])
swap(tx,ty),swap(x,y);
(ret += query(root,tid[tx],tid[x])) %= mod;
x = fa[tx],tx = top[x];
}
if(deep[x] < deep[y])
swap(x,y);
ret += query(root,tid[y],tid[x]);
return ret %= mod;
}
struct Ask{
int v,id,r;
int sigh;
void init(int V,int I,int S,int R){
v = V,id = I,sigh = S,r = R;
}
};
Ask ask[maxn*2];
bool cmp(Ask a,Ask b){
return a.v < b.v;
}
int ans[maxn];
int main(){
int q;
while(~scanf("%d %d",&n,&q)){
init(n);
int u,v;
for(int i=1;i<n;i++){
scanf("%d",&u);
Link(i,u);
}
splite();
sinit();
int r;
int len = 0;
for(int i=0;i<q;i++){
scanf("%d %d %d",&u,&v,&r);
ask[len++].init(u-1,i,-1,r);
ask[len++].init(v,i,1,r);
}
sort(ask,ask+len,cmp);
memset(ans,0,sizeof(ans));
int iter = 0;
for(int i=0;i<len;i++){
while(iter <= ask[i].v){
UPD(ROOT,iter++);
}
int &anw = ans[ask[i].id];
anw += ask[i].sigh * QUE(ask[i].r,ROOT);
((anw %= mod)+=mod)%=mod;
}
for(int i=0;i<q;i++){
printf("%d
",ans[i]%mod);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.