这道题就教会了我一点, 记得开 longlong
不然就是五十分, 我因为这个查错了一个小时
哭唧唧
题面 https://www.luogu.org/problemnew/show/P3178
- #include<cstring>
- #include<cstdio>
- #include<algorithm>
- #define ls(x) x<<1
- #define rs(x) x<<1|1
- #define ll long long
- using namespace std;
- const int N=4e5+6;
- ll res,ans;
- ll cnt,tot,m,n,root;
- ll sum[N],lg[N];
- ll size[N],top[N],v[N],vt[N],fa[N],head[N],dep[N],id[N],son[N];
- struct edge
- {
- ll nx,to;
- } e[N];
- void add_edge(ll a,ll b)
- {
- cnt++;e[cnt].nx=head[a];e[cnt].to=b;head[a]=cnt;
- cnt++;e[cnt].nx=head[b];e[cnt].to=a;head[b]=cnt;
- }
- void push_up(ll p)
- {
- sum[p]=sum[ls(p)]+sum[rs(p)];
- }
- void build(ll p,ll l,ll r)
- {
- if (l==r)
- {
- sum[p]=(ll)vt[l];
- return;
- }
- ll mid=(l+r)>>1;
- build(ls(p),l,mid);
- build(rs(p),mid+1,r);
- push_up(p);
- }
- void push_down(ll p,ll lenn)
- {
- lg[ls(p)]+=lg[p];
- lg[rs(p)]+=lg[p];
- sum[ls(p)]+=lg[p]*(lenn-(lenn>>1));
- sum[rs(p)]+=lg[p]*(lenn>>1);
- lg[p]=0;
- }
- void update(ll p,ll l,ll r,ll nl,ll nr,ll k)
- {
- if (nl<=l&&r<=nr)
- {
- lg[p]+=k;
- sum[p]+=k*(r-l+1);
- return;
- }
- ll mid=(l+r)>>1;
- push_down(p,(r-l+1));
- if (nl<=mid) update(ls(p),l,mid,nl,nr,k);
- if (nr>mid) update(rs(p),mid+1,r,nl,nr,k);
- push_up(p);
- }
- void query(ll p,ll l,ll r,ll xl,ll xr)
- {
- if (xl<=l&&r<=xr)
- {
- res+=sum[p];
- return;
- }
- push_down(p,(r-l+1));
- ll mid=(l+r)>>1;
- if (xl<=mid) query(ls(p),l,mid,xl,xr);
- if (xr>mid) query(rs(p),mid+1,r,xl,xr);
- }
- void dfs1(ll x,ll f,ll deep)
- {
- dep[x]=deep;
- fa[x]=f;
- size[x]=1;
- ll maxson=-1;
- for (ll i=head[x];i;i=e[i].nx)
- {
- ll y=e[i].to;
- if (y==fa[x]) continue;
- dfs1(y,x,deep+1);
- size[x]+=size[y];
- if (size[y]>maxson) {son[x]=y;maxson=size[y];}
- }
- }
- void dfs2(ll x,ll topf)
- {
- id[x]=++tot;
- vt[tot]=v[x];
- top[x]=topf;
- if (!son[x]) return;
- dfs2(son[x],topf);
- for (ll i=head[x];i;i=e[i].nx)
- {
- ll y=e[i].to;
- if (y==fa[x]||y==son[x]) continue;
- dfs2(y,y);
- }
- }
- void uprange(ll x,ll y,ll k)
- {
- while (top[x]!=top[y])
- {
- if (dep[top[x]]<dep[top[y]]) swap(x,y);
- update(1,1,n,id[top[x]],id[x],k);
- x=fa[top[x]];
- }
- if (dep[x]>dep[y]) swap(x,y);
- update(1,1,n,id[x],id[y],k);
- }
- void upson(ll x,ll y)
- {
- update(1,1,n,id[x],id[x]+size[x]-1,y);
- }
- ll querange(ll x,ll y)
- {
- ll ans=0;
- while(top[x]!=top[y])
- {
- if (dep[top[x]]<dep[top[y]]) swap(x,y);
- res=0;
- query(1,1,n,id[top[x]],id[x]);
- ans+=res;
- x=fa[top[x]];
- }
- if (dep[x]>dep[y]) swap(x,y);
- res=0;
- query(1,1,n,id[x],id[y]);
- ans+=res;
- return ans;
- }
- int main()
- {
- scanf("%lld%lld",&n,&m);
- for (ll i=1;i<=n;i++) scanf("%lld",&v[i]);
- for (ll i=1;i<n;i++)
- {
- ll x,y;
- scanf("%lld%lld",&x,&y);
- add_edge(x,y);
- }
- root=1;
- dfs1(root,0,1);
- dfs2(root,root);
- build(1,1,n);
- for (ll i=1;i<=m;i++)
- {
- ll opt,x,y;
- scanf("%lld",&opt);
- if (opt==1) {scanf("%lld%lld",&x,&y);uprange(x,x,y);}
- if (opt==2) {scanf("%lld%lld",&x,&y);upson(x,y);}
- if (opt==3) {scanf("%lld",&x);printf("%lld\n",querange(x,root));}
- }
- return 0;
- }
[HAOI2015] 树上操作
来源: http://www.bubuko.com/infodetail-3004342.html