題意:

　　一棵樹,

　　操作1.$path(a,b)$之間的點權$+k$

　　操作2.單點查詢

題解:

樹鏈剖分即可,注意代碼細節,雙向映射

主要是記錄一下板子

#include <string.h> #include <stdio.h> #include <algorithm> #define endl '\n' #define ll long long #define ull unsigned long long #define fi first #define se second #define pii pair<int,int> #define all(x) x.begin(),x.end() #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define rep(ii,a,b) for(int ii=a;ii<=b;++ii) #define per(ii,a,b) for(int ii=b;ii>=a;--ii) #define forn(ii,x) for(int ii=head[x];ii;ii=edge[ii].next) using namespace std; const int maxn=5e4+20,maxm=2e6+10; const int INF=0x3f3f3f3f; const ll mod=1e9+7; //head int casn,n,m,k; int num[maxn]; class segtree{public: #define nd node[now] #define ndl node[now<<1] #define ndr node[now<<1|1]int node[maxn*4],n;int *mp;void maketree(int s,int t,int now){if(s==t){nd=num[mp[s]];return ;}else nd=0;maketree(s,(s+t)/2,now<<1);maketree((s+t)/2+1,t,now<<1|1);}void init(int nn,int *mps){n=nn;mp=mps;maketree(1,n,1);}void update(int s,int t,int x){update(s,t,x,1,n,1);}int query(int pos){return query(pos,1,n,1);}void update(int s,int t,int x,int l,int r,int now=1){if(s<=l&&t>=r) {nd+=x;return ;}ndl+=nd,ndr+=nd;nd=0;int mid=(l+r)/2;if(s<=mid) update(s,t,x,l,mid,now<<1);if(t>mid) update(s,t,x,mid+1,r,now<<1|1);}int query(int pos,int l,int r,int now=1){if(l==r) return nd;ndl+=nd,ndr+=nd;nd=0;int mid=(l+r)/2;if(pos<=mid) return query(pos,l,mid,now<<1);else return query(pos,mid+1,r,now<<1|1);} }tree; namespace chain{struct data_e{int to,next;}edge[maxn<<1];int head[maxn],nume,mp[maxn];inline void addedge(int a,int b){edge[++nume]={b,head[a]};head[a]=nume;}int ltop[maxn],fa[maxn],deep[maxn];int sz[maxn],remp[maxn];int son[maxn],cnt;void init(){rep(i,1,n) head[i]=0;cnt=0,nume=1;}void dfs1(int now,int pre,int d){deep[now]=d,fa[now]=pre,sz[now]=1,son[now]=0;forn(i,now){int to=edge[i].to;if(to!=pre) {dfs1(to,now,d+1);sz[now]+=sz[to];if(sz[to]>sz[son[now]]) son[now]=to;}}}void dfs2(int now,int pre,int sp){ltop[now]=sp;mp[now]=++cnt;remp[cnt]=now;if(son[now]) dfs2(son[now],now,sp);forn(i,now){int to=edge[i].to;if(to!=son[now]&&to!=pre) dfs2(to,now,to);}}void update(int a,int b,int val){while(ltop[a]!=ltop[b]){if(deep[ltop[a]]<deep[ltop[b]])swap(a,b);tree.update(mp[ltop[a]],mp[a],val);a=fa[ltop[a]];}if(deep[a]>deep[b])swap(a,b);tree.update(mp[a],mp[b],val);} };int main() {while(~scanf("%d %d %d",&n,&m,&k)){rep(i,1,n) scanf("%d",num+i);chain::init();while(m--){int a,b;scanf("%d%d",&a,&b);chain::addedge(a,b);chain::addedge(b,a);}chain::dfs1(1,0,1);chain::dfs2(1,1,1);tree.init(n,chain::remp);while(k--){char x[10];int a,b,c;scanf("%s",x);if(x[0]=='Q'){scanf("%d",&a);printf("%d\n",tree.query(chain::mp[a]));}else if(x[0]=='I'){scanf("%d %d %d",&a,&b,&c);chain::update(a,b,c);}else {scanf("%d %d %d",&a,&b,&c);chain::update(a,b,-c);}}} }

?

轉載于:https://www.cnblogs.com/nervendnig/p/10638239.html

總結

以上是生活随笔為你收集整理的HDU 3966 树链剖分后线段树维护的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。