vector换链式前向星试试
by wxwoo @ 2019-07-10 22:22:16
dfs和qtre写挂了居然还有50...迷
贴份代码警示下后人
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=100010;
const ll INF=2147483647;
ll a[maxn],n,m,fa[maxn],id[maxn],tot,imap[maxn];
ll dep[maxn],s[maxn<<2],tag[maxn<<2],pd;
ll son[maxn],x,y,size[maxn],top[maxn];
vector<ll> e[maxn];
bool vis[maxn];
ll ls(ll p){return p<<1;}
ll rs(ll p){return p<<1|1;}
void dfs1(ll x,ll step)
{
dep[x] = step;
vis[x] = 1;
size[x] = 1;
ll tem = -1;
for(int i = 0;i < e[x].size();i++)
{
if(!vis[e[x][i]])
{
dfs1(e[x][i],step + 1);
fa[e[x][i]] = x;
size[x] += size[e[x][i]];
if(tem < size[e[x][i]])
{
tem = size[e[x][i]];
son[x] = e[x][i];
}
}
}
return;
}
void dfs2(ll x,ll topf)
{
top[x] = topf;
id[x] = ++tot;
imap[tot] = x;
vis[x] = 1;
if(!son[x])return;
dfs2(son[x],topf);
for(int i = 0;i < e[x].size();i++)
{
if(!vis[e[x][i]])
{
dfs2(e[x][i],e[x][i]);
}
}
return;
}
inline void build(ll p,ll l,ll r)
{
if(l == r)
{
s[p] = a[imap[l]];
return;
}
ll mid = (l + r)>>1;
build(ls(p),l,mid);
build(rs(p),mid + 1,r);
s[p] = s[ls(p)] + s[rs(p)];
return;
}
void push_down(ll p,ll l,ll r)
{
ll mid = (l + r)>>1;
tag[ls(p)] += tag[p];
tag[rs(p)] += tag[p];
s[ls(p)] += tag[p] * (mid - l + 1);
s[rs(p)] += tag[p] * (r - mid);
tag[p] = 0;
return;
}
void update(ll p,ll l,ll r,ll il,ll ir,ll det)
{
if(il <= l && ir >= r)
{
s[p] += det * (r - l + 1);
tag[p] += det;
return;
}
push_down(p,l,r);
ll mid = (l + r)>>1;
if(il <= mid)update(ls(p),l,mid,il,ir,det);
if(ir > mid)update(rs(p),mid + 1,r,il,ir,det);
s[p] = s[ls(p)] + s[rs(p)];
return;
}
ll qsum(ll p,ll l,ll r,ll il,ll ir)
{
if(il <= l && ir >= r)
{
return s[p];
}
push_down(p,l,r);
ll mid = (l + r)>>1;
ll res = 0;
if(il <= mid)res += qsum(ls(p),l,mid,il,ir);
if(ir > mid)res += qsum(rs(p),mid + 1,r,il,ir);
return res;
}
ll qtre(ll x,ll y)
{
ll res = 0;
while(top[x] != top[y])
{
if(dep[top[x]] < dep[top[y]])swap(x,y);
res += qsum(1,1,n,id[top[x]],id[x]);
x = fa[top[x]];
}
if(dep[x] > dep[y])swap(x,y);
res += qsum(1,1,n,id[x],id[y]);
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i = 1;i <= n;i++)cin>>a[i];
for(int i = 1;i < n;i++)
{
cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
}
dfs1(1,1);
fa[1] = 1;
memset(vis,0,sizeof(vis));
dfs2(1,1);
build(1,1,n);
while(m--)
{
cin>>pd;
if(pd == 1)
{
cin>>x>>y;
update(1,1,n,id[x],id[x],y);
}
else if(pd == 2)
{
cin>>x>>y;
update(1,1,n,id[x],id[x] + size[x] - 1,y);
}
else
{
cin>>x;
printf("%lld\n",qtre(1,x));
}
}
return 0;
}
```
by Frozencode @ 2019-07-10 22:54:49