?題意:給你一棵樹,要求你維護兩個操作.

?0:某子樹的所有節點權值加上一個數.

?1:求某些鏈并集的權值和.

?對于第一個操作,大力樹鏈剖分加線段樹.

?對于第二個操作,考慮到鏈的數量很少,可以容斥.

代碼:

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<queue> #include<set> #include<map> #include<iomanip> using namespace std; #define LL long long #define up(i,j,n) for(int i=j;i<=n;i++) #define pii pair<int,int> #define db double #define eps 1e-4 #define FILE "dealing" int read(){int x=0,f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0',ch=getchar();}return x*f; } const LL maxn=1000000,inf=1000000000000000LL,limit=20000; bool cmin(int& a,int b){return a>b?a=b,true:false;} bool cmax(int& a,int b){return a<b?a=b,true:false;} int n,m; struct node{int y,next; }e[maxn]; int len=0,linkk[maxn],top[maxn],fa[maxn],dep[maxn],pre[maxn],low[maxn]; void insert(int x,int y){e[++len].y=y;e[len].next=linkk[x];linkk[x]=len; } void init(){n=read();up(i,1,n-1){int x=read(),y=read();insert(x,y);insert(y,x);} } namespace treepou{int dfs_clock=0,siz[maxn],son[maxn];void dfs1(int x){siz[x]=1;for(int i=linkk[x];i;i=e[i].next){if(e[i].y==fa[x])continue;fa[e[i].y]=x;dep[e[i].y]=dep[x]+1;dfs1(e[i].y);siz[x]+=siz[e[i].y];if(siz[e[i].y]>siz[son[x]])son[x]=e[i].y;}}void dfs2(int x){pre[x]=++dfs_clock;if(son[x]){top[son[x]]=top[x];dfs2(son[x]);}for(int i=linkk[x];i;i=e[i].next){if(e[i].y==son[x]||e[i].y==fa[x])continue;top[e[i].y]=e[i].y;dfs2(e[i].y);}low[x]=dfs_clock;}void solve(){dfs1(1);top[1]=1;dfs2(1);} }; namespace SegTree{int del[maxn],siz[maxn],sum[maxn],L,R,key,id[maxn];int Add(int x,int d){del[x]+=d;sum[x]+=siz[x]*d;}void updata(int x){sum[x]=sum[x<<1]+sum[x<<1|1];}void pushdown(int x){if(del[x]){Add(x<<1,del[x]);Add(x<<1|1,del[x]);del[x]=0;}}void change(int o,int l,int r){if(l>R||r<L)return;if(l>=L&&r<=R){Add(o,key);return;}int mid=(l+r)>>1;pushdown(o);change(o<<1,l,mid);change(o<<1|1,mid+1,r);updata(o);}void Change(int x,int y,int Del){L=x,R=y,key=Del;change(1,1,n);}int query(int l,int r,int o){if(l>R||r<L)return 0;if(l>=L&&r<=R)return sum[o];int mid=(l+r)>>1;pushdown(o);return query(l,mid,o<<1)+query(mid+1,r,o<<1|1);}int Query(int x,int y){if(x>y)swap(x,y);L=x,R=y;return query(1,n,1);}void build(int l,int r,int o){if(l==r){siz[o]=1;sum[o]=0;return;}int mid=(l+r)>>1;build(l,mid,o<<1);build(mid+1,r,o<<1|1);siz[o]=siz[o<<1]+siz[o<<1|1];}void Build(){up(i,1,n)id[pre[i]]=i;build(1,n,1);} } namespace solve{pii getlian(int x,int y){int f1,f2;int sum=0;while(true){if(dep[x]>dep[y])swap(x,y);f1=top[x],f2=top[y];if(f1==f2){sum+=SegTree::Query(pre[x],pre[y]);return make_pair(x,sum);}if(dep[f1]>dep[f2])swap(x,y),swap(f1,f2);sum+=SegTree::Query(pre[f2],pre[y]);y=fa[f2];}}int getlca(int x,int y){int f1,f2;while(true){if(dep[x]>dep[y])swap(x,y);f1=top[x],f2=top[y];if(f1==f2)return x;if(dep[f1]>dep[f2])swap(x,y),swap(f1,f2);y=fa[f2];}}pii t[maxn];int query(){int m=read();up(i,1,m){t[i].first=read(),t[i].second=read();if(dep[t[i].first]>dep[t[i].second])swap(t[i].first,t[i].second);}pii y=make_pair(0,0);int ans=0;for(int i=1;i<(1<<m);i++){int g=-1,flag=0;up(j,1,m){if(i&(1<<j-1))g*=-1;else continue;if(!flag)y=t[j],flag=1;else {int w=getlca(y.second,t[j].second);if(dep[w]<dep[y.first]||dep[w]<dep[t[j].first]){y=make_pair(0,0);break;}else {if(dep[y.first]<dep[t[j].first])y.first=t[j].first;y.second=w;}}}//printf("%d %d %d\n",g,y.first,y.second);if(y.first)ans+=g*getlian(y.first,y.second).second;}return ans;} };int main(){freopen(FILE".in","r",stdin);freopen(FILE".out","w",stdout);init();treepou::solve();//樹剖 返回top,dep,faSegTree::Build();//prepare SegTree int m=read();while(m--){int ch=read();if(ch==0){int x=read(),del=read();SegTree::Change(pre[x],low[x],del);}else printf("%d\n",solve::query()&((1<<31)-1));}return 0; }

　　

轉載于:https://www.cnblogs.com/chadinblog/p/6492672.html

總結

以上是生活随笔為你收集整理的bzoj3589 动态树的全部內容，希望文章能夠幫你解決所遇到的問題。

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