[판자고] P3384 [모형] 경중 체인 분해/나무 체인 분해 모형 문제
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//
using namespace std;
const int INF = 0x3f3f3f3f;//1.06e9
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
const int mod3 = 1e9;
const double PI = acos ( -1 );
const double eps = 1e-8;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned uint;
const int sq5 = 616991993;
inline int read()
{
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {
X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
#define ms(x,n) memset(x,n,sizeof(x))
#define debug(x) printf("***%d***
",x)
#define pii pair
#define X first
#define Y second
#define pb push_back
#define mid ((l+r)>>1)
#define ls k<<1
#define rs k<<1|1
#define lowbit a&(-a)
const int maxn = 2e5 + 10;
//
int n , m ,r ,mod;
int e ,beg[maxn],nx[maxn],to[maxn],w[maxn],wt[maxn];
// ,w[],wt[]
int a[maxn<<2],lazy[maxn<<2];
//
int son[maxn] , id[maxn] , fa[maxn] , cnt , dep[maxn] , sz[maxn ], top[maxn];
// dfs
int res ;// ;
inline void add(int u,int v)
{
//
to[++e] = v;
nx[e] = beg[u];
beg[u] = e;
}
inline void pushdown(int k,int lenn)
{
//lazy
lazy[ls] += lazy[k];
lazy[rs] += lazy[k];
a[ls] += lazy[k]*(lenn-(lenn>>1));
a[rs] += lazy[k]*(lenn>>1);
a[ls]%=mod;
a[rs]%=mod;
lazy[k] = 0;
}
inline void build(int k,int l,int r)
{
if(l==r)
{
a[k] = wt[l];
a[k]%=mod;
return ;
}
build(ls,l,mid);
build(rs,mid+1,r);
a[k] = (a[ls]+a[rs])%mod;
}
inline void query(int k,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
{
res+=a[k];
res%=mod;
return ;
}
else
{
if(lazy[k])pushdown(k,r-l+1);
if(L<=mid)query(ls,l,mid,L,R);
if(R>mid)query(rs,mid+1,r,L,R);
}
}
inline void update(int k,int l,int r,int L,int R,int x)
{
if(L<=l&&r<=R)
{
lazy[k]+=x;
a[k]+=x*(r-l+1);
}
else
{
if(lazy[k])pushdown(k,r-l+1);
if(L<=mid)update(ls,l,mid,L,R,x);
if(R>mid)update(rs,mid+1,r,L,R,x);
a[k] = (a[ls]+a[rs])%mod;
}
}
//
inline int chain_que(int u,int v)
{
int ans =0 ;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]])swap(u,v);// x
res = 0;
query(1,1,n,id[top[u]],id[u]);//ans+=x x
ans += res;
ans%=mod;
u = fa[top[u]];//x x
}
//
if(dep[u]>dep[v])swap(u,v);// x
res =0;
query(1,1,n,id[u],id[v]);
ans += res;
return ans%mod;
}
inline void chain_update(int u,int v,int x)
{
x%=mod;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]])swap(u,v);
update(1,1,n,id[top[u]],id[u],x);
u = fa[top[u]];
}
if(dep[u]>dep[v])swap(u,v);
update(1,1,n,id[u],id[v],x);
}
inline int str_que(int k)
{
res =0 ;
query(1,1,n,id[k],id[k]+sz[k]-1);// id[k]+sz[k]+1
return res;
}
inline void str_update(int k,int x)
{
update(1,1,n,id[k],id[k]+sz[k]-1,x);
}
inline void dfs1(int k,int f,int deep)
{
dep[k] = deep;
fa[k] = f;
sz[k] =1;
int maxson =-1;//
for(int i=beg[k];i;i=nx[i])
{
int y = to[i];
if(y == f)continue;// continue
dfs1(y,k,deep+1);
sz[k] +=sz[y];//
if(sz[y]>maxson)son[k]= y,maxson=sz[y];
}
}
inline void dfs2(int k,int topf)//x ,topf
{
id[k]=++cnt;
wt[cnt] = w[k];
top[k] = topf;
if(!son[k])return ;
dfs2(son[k],topf);
for(int i = beg[k];i;i=nx[i])
{
int y =to[i];
if(y==fa[k]||y==son[k])continue;
dfs2(y,y);
}
}
int main()
{
cin>>n>>m>>r>>mod;
for(int i=1;i<=n;++i)
{
w[i] = read();
}
for(int i =1;i<n;++i)
{
int a,b;
a=read();b=read();
add(a,b);add(b,a);
}
dfs1(r,0,1);
dfs2(r,r);
build(1,1,n);
while(m--)
{
int k,x,y,z;
k = read();
if(k==1)
{
x=read();y=read();z=read();
chain_update(x,y,z);
}
else if(k==2)
{
x = read();y = read();
printf("%d
",chain_que(x,y));
}
else if(k==3)
{
x=read();y=read();
str_update(x,y);
}
else
{
x=read();
printf("%d
",str_que(x));
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BZOJ2631]tree(LCT)전송문 판자 문제×+ 의 조작은 약간의 기교를 사용했다.너도 선승후승과 선승후승은 다르다는 것을 발견했을 것이다.처음에는 표시를 할 때 먼저 밑에 예전의 표시를 해야 한다고 생각했는데, 밑에 표시가 있으면 어떡하지?...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.