鏈接：https://ac.nowcoder.com/acm/contest/180/E
來源：牛客網(wǎng)

樹上路徑
時間限制：C/C++ 2秒，其他語言4秒
空間限制：C/C++ 262144K，其他語言524288K
64bit IO Format: %lld
題目描述
給出一個n個點的樹，1號節(jié)點為根節(jié)點，每個點有一個權(quán)值
你需要支持以下操作
1.將以u為根的子樹內(nèi)節(jié)點(包括u)的權(quán)值加val
2.將(u, v)路徑上的節(jié)點權(quán)值加val
3.詢問(u, v)路徑上節(jié)點的權(quán)值兩兩相乘的和

輸入描述:
第一行兩個整數(shù)n, m，表示樹的節(jié)點個數(shù)以及操作個數(shù)

接下來一行n個數(shù)，表示每個節(jié)點的權(quán)值

接下來n - 1行，每行兩個整數(shù)(u, v)，表示(u, v)之間有邊

接下來m行
開始有一個數(shù)opt，表示操作類型
若opt = 1，接下來兩個整數(shù)表示u, val
若opt = 2，接下來三個整數(shù)表示(u, v), val
若opt = 3，接下來兩個整數(shù)表示(u, v)
含義均如題所示
輸出描述:
對于每個第三種操作，輸出一個數(shù)表示答案，對10^9+710
9
+7取模
示例1
輸入
復(fù)制
3 8
5 3 1
1 2
1 3
3 1 2
3 1 3
3 2 3
1 1 2
2 1 3 2
3 1 2
3 1 3
3 2 3
輸出
復(fù)制
15
5
23
45
45
115
說明
第一組詢問結(jié)果：3 * 5 = 15
第二組詢問結(jié)果：1 * 5 = 5
第三組詢問結(jié)果：3 * 5 + 1 * 5 + 3 * 1 = 23
備注:
對于30 %30%的數(shù)據(jù)，n, m \leqslant 100n,m?100
對于100 %100%的數(shù)據(jù)，n, m \leqslant 10^5n,m?10
5

設(shè)a_ia
i
?
表示讀入的第i個節(jié)點的權(quán)值以及每次修改的權(quán)值，保證a_i \leqslant 10^4a
i
?
?10
4

保證不會有負數(shù)

思路：
很顯然的樹鏈剖分題，

前兩個操作都是樹鏈剖分的常規(guī)操作，

我們來看下第三個操作，我們假設(shè)詢問的路徑上有3個節(jié)點，權(quán)值分別是 a，b，c，，我們所求的結(jié)果就是ab+ac+b*c 來看下如何得到這個結(jié)果呢？

即我們可以維護區(qū)間的兩個值（節(jié)點權(quán)值的sum和，和節(jié)點權(quán)值平方的sum）來得出區(qū)間的兩兩相乘再相加的結(jié)果（即操作3的輸出）。

我們知道線段樹維護區(qū)間sum和是很容易的，這里我就不講了，那么如何維護權(quán)值平方的sum呢（即當區(qū)間中每一個值都加上t，如何方便得到新的平方sum和）？

我們假設(shè)一次更改的區(qū)間有三個節(jié)點，權(quán)值分別是a,b,c

這樣我們可以看出，我們可以從線段樹維護的兩個值 ：sum和平方sum 來更新平方sum

例如區(qū)間加上t

新的平方sum= 更新前的平方sum+ 區(qū)間長度 乘 t 乘 t + 2t 乘 權(quán)值sum和。

這樣就可以寫本題了，記得pushdown的時候線段樹的laze標記一定是+= 而不是 =

細節(jié)見代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;} inline void getInt(int* p); const int maxn = 100010; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ const ll mod=1e9+7ll; std::vector<int> son[maxn]; ll w[maxn]; ll wt[maxn]; int id[maxn]; int SZ[maxn]; int wson[maxn]; int top[maxn]; int fa[maxn]; int n,m; int dep[maxn]; int cnt; void init() {cnt=0; } void dfs1(int x,int pre,int step) {fa[x]=pre;dep[x]=step;SZ[x]=1;int maxson=-1;for(auto & t:son[x]){if(t!=pre){dfs1(t,x,step+1);SZ[x]+=SZ[t];if(SZ[t]>maxson){maxson=SZ[t];wson[x]=t;}}} }void dfs2(int x,int topf) {top[x]=topf;id[x]=++cnt;wt[cnt]=w[x];if(wson[x])dfs2(wson[x],topf);elsereturn ;for(auto &t :son[x]){if(t==wson[x]||t==fa[x]){continue;}dfs2(t,t);} } struct node {ll l,r;ll sum;ll csum;ll laze; }segment_tree[maxn<<2]; void pushup(int rt) {segment_tree[rt].sum=(segment_tree[rt<<1].sum+segment_tree[rt<<1|1].sum)%mod;segment_tree[rt].csum=(segment_tree[rt<<1].csum+segment_tree[rt<<1|1].csum)%mod; } void build(int rt,int l,int r) {segment_tree[rt].l=l;segment_tree[rt].r=r;segment_tree[rt].laze=0ll;if(l==r){segment_tree[rt].sum=wt[l];segment_tree[rt].csum=wt[l]*wt[l]%mod;return ;}int mid=(l+r)>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);pushup(rt); } void pushdown(int rt) {if(segment_tree[rt].laze){ll val=segment_tree[rt].laze%mod;segment_tree[rt].laze=0ll;segment_tree[rt<<1].csum+=((segment_tree[rt<<1].r-segment_tree[rt<<1].l+1)*val%mod*val%mod+2ll*val%mod*(segment_tree[rt<<1].sum)%mod)%mod;segment_tree[rt<<1].csum%=mod;segment_tree[rt<<1].sum+=(segment_tree[rt<<1].r-segment_tree[rt<<1].l+1)*val%mod;segment_tree[rt<<1].sum%=mod;segment_tree[rt<<1].laze+=val;segment_tree[rt<<1].laze%=mod;segment_tree[rt<<1|1].csum+=((segment_tree[rt<<1|1].r-segment_tree[rt<<1|1].l+1)*val%mod*val%mod+2ll*val%mod*(segment_tree[rt<<1|1].sum)%mod)%mod;segment_tree[rt<<1|1].csum%=mod;segment_tree[rt<<1|1].sum+=(segment_tree[rt<<1|1].r-segment_tree[rt<<1|1].l+1)*val%mod;segment_tree[rt<<1|1].sum%=mod;segment_tree[rt<<1|1].laze+=val;segment_tree[rt<<1|1].laze%=mod;} }void update(int rt,int l,int r,ll val) {val%=mod;if(segment_tree[rt].l>=l&&segment_tree[rt].r<=r){segment_tree[rt].csum+=((segment_tree[rt].r-segment_tree[rt].l+1)*val%mod*val%mod+2ll*val%mod*segment_tree[rt].sum%mod)%mod;segment_tree[rt].csum%=mod;segment_tree[rt].laze+=val;segment_tree[rt].laze%=mod;segment_tree[rt].sum+=(segment_tree[rt].r-segment_tree[rt].l+1)*val%mod;segment_tree[rt].sum%=mod;return ;}pushdown(rt);int mid=segment_tree[rt].r+segment_tree[rt].l;mid>>=1;if(mid>=l){update(rt<<1,l,r,val);}if(mid<r){update(rt<<1|1,l,r,val);}pushup(rt); }void upson(int x,ll val) {val%=mod;update(1,id[x],id[x]+SZ[x]-1,val); } void uprange(int x,int y,ll val) {while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]){swap(x,y);}update(1,id[top[x]],id[x],val);x=fa[top[x]];}if(dep[x]>dep[y]){swap(x,y);}update(1,id[x],id[y],val); } ll ask1(int rt,int l,int r) {if(segment_tree[rt].l>=l&&segment_tree[rt].r<=r){return segment_tree[rt].sum%mod;}pushdown(rt);int mid=(segment_tree[rt].l+segment_tree[rt].r)>>1;ll res=0ll;if(mid>=l){res+=ask1(rt<<1,l,r);res%=mod;}if(mid<r){res+=ask1(rt<<1|1,l,r);res%=mod;}return res; } ll ask2(int rt,int l,int r) {if(segment_tree[rt].l>=l&&segment_tree[rt].r<=r){return segment_tree[rt].csum%mod;}pushdown(rt);int mid=(segment_tree[rt].l+segment_tree[rt].r)>>1;ll res=0ll;if(mid>=l){res+=ask2(rt<<1,l,r);res%=mod;}if(mid<r){res+=ask2(rt<<1|1,l,r);res%=mod;}return res; }ll qrange(int x,int y) {ll sum1=0ll;ll sum2=0ll;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);sum1=(sum1+ask1(1,id[top[x]],id[x]))%mod;sum2=(sum2+ask2(1,id[top[x]],id[x]))%mod;x=fa[top[x]];}if(dep[x]>dep[y]){swap(x,y);}sum1=(sum1+ask1(1,id[x],id[y]))%mod;sum2=(sum2+ask2(1,id[x],id[y]))%mod;ll res=(sum1*sum1%mod-sum2+mod)%mod;res=(res*powmod(2ll,mod-2ll,mod))%mod;return res; } int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);gbtb;cin>>n>>m;repd(i,1,n){cin>>w[i];}int u,v;repd(i,2,n){cin>>u>>v;son[u].pb(v);son[v].pb(u);}init();dfs1(1,-1,0);dfs2(1,1);build(1,1,n);int op;ll c;while(m--){cin>>op;if(op==1){cin>>u>>c;upson(u,c);}else if(op==2){cin>>u>>v>>c;uprange(u,v,c);}else if(op==3){cin>>u>>v;cout<<qrange(u,v)<<endl;}}return 0; }inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}}else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

轉(zhuǎn)載于:https://www.cnblogs.com/qieqiemin/p/11299530.html

總結(jié)

以上是生活随笔為你收集整理的牛客练习赛26 E-树上路径 （树链剖分+线段树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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