[판자고] P3384 [모형] 경중 체인 분해/나무 체인 분해 모형 문제

51052 단어 판자창고lct
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; }

좋은 웹페이지 즐겨찾기