題目鏈接：點擊查看

題目大意：給出一棵由n個點組成的樹，每個點都有一個權(quán)值，接下來有k次操作，每次操作分為下面幾種類型：

I u v x：將u-v這條路徑上的所有點權(quán)值加上x

D u v x：將u-v這條路徑上的所有點權(quán)值減去x

Q x：查詢點x的權(quán)值

題目分析：因為又涉及到了樹上路徑的問題，這個題涉及到的是路徑上的點權(quán)修改，很容易和線段樹的區(qū)間修改聯(lián)想到一起，所以我們還是先剖一下，剖完之后直接建立線段樹，然后這個問題就轉(zhuǎn)換成了最簡單的sum線段樹的維護(hù)了，也是好久沒寫區(qū)間更新的線段樹了，練習(xí)了一下lazy標(biāo)記的下傳問題，這個題目是點權(quán)，和之前邊權(quán)的題目有點不太一樣的地方是關(guān)于沿著樹鏈修改的時候，每個點都要遍歷到，也就是說當(dāng)a==b的時候不能直接返回了，單個點也是需要修改的，具體的看代碼注釋吧

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=5e4+100;int n,m,w;int val[N];vector<int>node[N];int deep[N],fa[N],son[N],num[N];void dfs1(int u,int f,int dep) {deep[u]=dep;son[u]=-1;num[u]=1;fa[u]=f;for(auto v:node[u]){if(v==f)continue;dfs1(v,u,dep+1);num[u]+=num[v];if(son[u]==-1||num[son[u]]<num[v])son[u]=v;} }int id[N],idd[N],top[N],cnt;//id[節(jié)點]=編號 idd[編號]=節(jié)點 void dfs2(int u,int f,int root) {top[u]=root;id[u]=++cnt;idd[cnt]=u;if(son[u]!=-1)dfs2(son[u],u,root);for(auto v:node[u]){if(v==f||v==son[u])continue;dfs2(v,u,v);} }struct Node {int l,r,lazy,sum;int mid(){return l+r>>1;}int cal_len(){return r-l+1;} }tree[N<<2];void pushup(int k) {tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; }void pushdown(int k) {int lz=tree[k].lazy;tree[k<<1].sum+=tree[k<<1].cal_len()*lz;tree[k<<1|1].sum+=tree[k<<1|1].cal_len()*lz;tree[k<<1].lazy+=lz;tree[k<<1|1].lazy+=lz;tree[k].lazy=0; }void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].lazy=0;if(l==r){tree[k].sum=val[idd[l]];return;}int mid=tree[k].mid();build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k); }void update(int k,int l,int r,int val) {if(tree[k].r<l||tree[k].l>r)return;if(tree[k].l>=l&&tree[k].r<=r){tree[k].lazy+=val;tree[k].sum+=tree[k].cal_len()*val;return;}if(tree[k].lazy)pushdown(k);update(k<<1,l,r,val);update(k<<1|1,l,r,val);pushup(k); }int query(int k,int pos) {if(tree[k].l==tree[k].r)return tree[k].sum;if(tree[k].lazy)pushdown(k);int mid=tree[k].mid();if(mid>=pos)return query(k<<1,pos);elsereturn query(k<<1|1,pos); }void solve(int a,int b,int val) {while(top[a]!=top[b]){if(deep[top[a]]<deep[top[b]])swap(a,b);update(1,id[top[a]],id[a],val);a=fa[top[a]];} // if(a==b) //這里特意打了注釋，就是為了區(qū)分點權(quán)和邊權(quán)的區(qū)別的，可以好好理解一下為什么要將這句話注釋掉 // return;if(deep[a]<deep[b])swap(a,b);update(1,id[b],id[a],val);return; }void init() {for(int i=1;i<=n;i++)node[i].clear();cnt=0; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%d%d%d",&n,&m,&w)!=EOF){init();for(int i=1;i<=n;i++)scanf("%d",val+i);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}dfs1(1,0,0);dfs2(1,0,1);build(1,1,n);while(w--){char s[5];scanf("%s",s);if(s[0]=='I'){int u,v,w;scanf("%d%d%d",&u,&v,&w);solve(u,v,w);}else if(s[0]=='D'){int u,v,w;scanf("%d%d%d",&u,&v,&w);solve(u,v,-w);}else{int x;scanf("%d",&x);printf("%d\n",query(1,id[x]));}}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 3966 Aragorn's Story(树链剖分+线段树)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。