读入好像出了什么毛病
by Evan704 @ 2018-12-07 19:52:29
Orz 初一树剖神仙
by Nova_守门员 @ 2018-12-07 20:30:44
@[Nova_守门员](/space/show?uid=110976) 话说我有个拿py写数据结构的想法~~我决定还是省省吧~~
by tt66ea @ 2018-12-07 20:31:33
@[tt66ea](/space/show?uid=103603) 会Py的dalao%%%
by Nova_守门员 @ 2018-12-07 20:34:21
@[Nova_守门员](/space/show?uid=110976) 您才会啊QAQ
py我还要找我爸学还不一定会教……
by tt66ea @ 2018-12-07 20:34:54
@[tt66ea](/space/show?uid=103603) 我不会py
by Nova_守门员 @ 2018-12-07 20:35:09
@[Nova_守门员](/space/show?uid=110976) 我觉得py的强制缩进很好qwq!
还有个玄学东西叫做交互命令行……
by tt66ea @ 2018-12-07 20:39:08
@[tt66ea](/space/show?uid=103603) Orz
by Nova_守门员 @ 2018-12-07 20:52:26
蒟蒻代码
```cpp
#include<bits/stdc++.h>
using namespace std;
//数组--------------------------------------------
struct Edge{
long long v,nxt;
}e[400001];
long long a[200001];
long long fa[200001];
long long id[200001];
long long siz[200001];
long long son[200001];
long long dep[200001];
long long top[200001];
long long head[200001];
long long node[200001];
long long cnt,n,m,tot;
long long tree[800001],laz[800001],sum;
//建图---------------------------------------
void addEdge(long long u,long long v){
e[tot].v = v;
e[tot].nxt = head[u];
head[u] = tot;
++ tot;
}
inline void ad(long long u,long long v){
addEdge(u,v);
addEdge(v,u);
}
//线段树---------------------------------------
void build(long long id,long long l,long long r){
if(l==r){
tree[id]=node[l];
return;
}
long long mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
tree[id]=tree[id*2]+tree[id*2+1];
}
void pushdown(long long id,long long l,long long r){
if(laz[id]){
tree[id*2]+=laz[id]*((l+r)/2-l+1);
tree[id*2+1]+=laz[id]*(r-((l+r)/2+1)+1);
laz[id*2]+=laz[id];
laz[id*2+1]+=laz[id];
laz[id]=0;
}
}
void change(long long id,long long l,long long r,long long a,long long b,long long c){
if(a<=l&&b>=r){
tree[id]+=c*(r-l+1);
laz[id]+=c;
return;
}
pushdown(id,l,r);
long long mid=(l+r)/2;
if(a<=mid)
change(id*2,l,mid,a,b,c);
if(b>mid)
change(id*2+1,mid+1,r,a,b,c);
tree[id]=tree[id*2]+tree[id*2+1];
}
void question(long long id,long long l,long long r,long long a,long long b){
if(a<=l&&b>=r){
sum+=tree[id];
return;
}
pushdown(id,l,r);
long long mid=(l+r)/2;
if(a<=mid) question(id*2,l,mid,a,b);
if(b>mid) question(id*2+1,mid+1,r,a,b);
}
//预处理---------------------------------------
void dfs1(long long u,long long father,long long depth){
siz[u]=1;
fa[u]=father;
dep[u]=depth;
long long maxn=-1;
for(long long i=head[u];i!=-1;i=e[i].nxt){
long long v=e[i].v;
if(v==father) continue;
dfs1(v,u,depth+1);
siz[u]+=siz[v];
if(siz[v]>maxn){
maxn=siz[v];
son[u]=v;
}
}
}
void dfs2(long long u,long long ltop){
id[u]=++cnt;
node[cnt]=a[u];
top[u]=ltop;
if(!son[u]) return;
dfs2(son[u],ltop);
for(long long i=head[u];i!=-1;i=e[i].nxt){
long long v=e[i].v;
if(v==fa[u]||v==son[u])
continue;
dfs2(v,v);
}
}
//询问&修改---------------------------------------------------
long long query1(long long x,long long y){
long long ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
sum=0;
question(1,1,n,id[top[x]],id[x]);
ans=(ans+sum);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
sum=0;
question(1,1,n,id[x],id[y]);
ans=(ans+sum);
return ans;
}
void update1(long long x,long long y,long long z){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
change(1,1,n,id[top[x]],id[x],z);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
change(1,1,n,id[x],id[y],z);
}
long long query2(long long x){
sum=0;
question(1,1,n,id[x],id[x]+siz[x]-1);
return sum;
}
void update2(long long x,long long y){
change(1,1,n,id[x],id[x]+siz[x]-1,y);
}
//主程序------------------------------------------------------
int main(){
long long op,x,y,z;
scanf("%lld%lld",&n,&m);
memset(head,-1,sizeof(head));
for(long long i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(long long i=1;i<n;i++){
scanf("%lld%lld",&x,&y);
ad(x,y);
}
dfs1(1,-1,1);
dfs2(1,1);
build(1,1,n);
for(long long i=1;i<=m;i++){
scanf("%lld",&op);
if(op==1){
scanf("%lld%lld",&x,&y);
change(1,1,n,id[x],id[x],y);
}
if(op==2){
scanf("%lld%lld",&x,&y);
update2(x,y);
}
if(op==3){
scanf("%lld",&x);
printf("%lld\n",query1(1,x));
}
}
}
```
by tylon2006 @ 2018-12-12 00:24:39
请全开long long
by tylon2006 @ 2018-12-12 00:25:36