嘉兴网站建设推荐,网站架构设计英文翻译,wordpress go 跳转,广州应用网站设计4034: [HAOI2015]T2 Description 有一棵点数为 N 的树#xff0c;以点 1 为根#xff0c;且树点有边权。然后有 M 个 操作#xff0c;分为三种#xff1a;操作 1 #xff1a;把某个节点 x 的点权增加 a 。操作 2 #xff1a;把某个节点 x 为根的子树中所有点的点权都增加… 4034: [HAOI2015]T2 Description 有一棵点数为 N 的树以点 1 为根且树点有边权。然后有 M 个 操作分为三种 操作 1 把某个节点 x 的点权增加 a 。 操作 2 把某个节点 x 为根的子树中所有点的点权都增加 a 。 操作 3 询问某个节点 x 到根的路径中所有点的点权和。 Input 第一行包含两个整数 N, M 。表示点数和操作数。 接下来一行 N 个整数表示树中节点的初始权值。 接下来 N-1 行每行三个正整数 fr, to 表示该树中存在一条边 (fr, to) 。 再接下来 M 行每行分别表示一次操作。其中第一个数表示该操 作的种类 1-3 之后接这个操作的参数 x 或者 x a 。 Output 对于每个询问操作输出该询问的答案。答案之间用换行隔开。 Sample Input 5 5 1 2 3 4 5 1 2 1 4 2 3 2 5 3 3 1 2 1 3 5 2 1 2 3 3 Sample Output 6 9 13 HINT 对于 100% 的数据 N,M100000 且所有输入数据的绝对值都不 会超过 10^6 。 Source 题解 裸题了 代码来自HZWER #includecmath
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define inf 1000000000
#define mod 1000000000
using namespace std;
int read()
{int x0,f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){xx*10ch-0;chgetchar();}return x*f;
}
int n,m,cnt;
int last[100005];
int id,pos[100005],mx[100005],v[100005];
int bl[100005],size[100005],fa[100005];
ll tag[400005],sum[400005];
struct edge{int to,next;
}e[200005];
void insert(int u,int v)
{e[cnt](edge){v,last[u]};last[u]cnt;e[cnt](edge){u,last[v]};last[v]cnt;
}
void dfs(int x)
{size[x]1;for(int ilast[x];i;ie[i].next)if(e[i].to!fa[x]){fa[e[i].to]x;dfs(e[i].to);size[x]size[e[i].to];}
}
void dfs2(int x,int cha)
{bl[x]cha;pos[x]mx[x]id;int k0;for(int ilast[x];i;ie[i].next)if(e[i].to!fa[x]size[e[i].to]size[k])ke[i].to;if(k){dfs2(k,cha);mx[x]max(mx[x],mx[k]);}for(int ilast[x];i;ie[i].next)if(e[i].to!fa[x]e[i].to!k){dfs2(e[i].to,e[i].to);mx[x]max(mx[x],mx[e[i].to]);}
}
void pushdown(int l,int r,int k)
{if(lr)return;int mid(lr)1;ll ttag[k];tag[k]0;tag[k1]t;tag[k1|1]t;sum[k1]t*(mid-l1);sum[k1|1]t*(r-mid);
}
void add(int k,int l,int r,int x,int y,ll val)
{if(tag[k])pushdown(l,r,k);if(lxyr){tag[k]val;sum[k](r-l1)*val;return;}int mid(lr)1;if(xmid)add(k1,l,mid,x,min(mid,y),val);if(ymid1)add(k1|1,mid1,r,max(mid1,x),y,val);sum[k]sum[k1]sum[k1|1];
}
ll query(int k,int l,int r,int x,int y)
{if(tag[k])pushdown(l,r,k);if(lxyr)return sum[k];int mid(lr)1;ll ans0;if(xmid)ansquery(k1,l,mid,x,min(mid,y));if(ymid1)ansquery(k1|1,mid1,r,max(mid1,x),y);return ans;
}
ll query(int x)
{ll ans0;while(bl[x]!1){ansquery(1,1,n,pos[bl[x]],pos[x]);xfa[bl[x]];}ansquery(1,1,n,1,pos[x]);return ans;
}
int main()
{nread();mread();for(int i1;in;i)v[i]read();for(int i1;in;i){int uread(),vread();insert(u,v);}dfs(1);dfs2(1,1);for(int i1;in;i)add(1,1,n,pos[i],pos[i],v[i]);int opt,x,a;while(m--){optread();xread();if(opt1){aread();add(1,1,n,pos[x],pos[x],a);}if(opt2){aread();add(1,1,n,pos[x],mx[x],a);}if(opt3)printf(%lld\n,query(x));}return 0;
} 转载于:https://www.cnblogs.com/zxhl/p/5267187.html
