Lvat_s Blog

首先我们排个序，然后列一个dp方程

设$f[i][j]$为前i小的糖果至少匹配j个药片的数量

那么我们可以利用单调性把这个dp优化到$O(n^2)$

之后我们发现这个可能会重复统计

我们考虑怎么消除重复的部分

首先一个糖果匹配后面药片的总数为$n!$

然后其中重复统计的个数为之后计算的所有dp数组的值乘上一个组合数

那么我们倒着容斥就做完了

详见代码

#include<cstdio>
#include<algorithm>
using namespace std;

const int N=2005;
const long long P=1000000009ll;

int n,m,k;
long long a[N],b[N],C[N][N],fac[N],f[N][N];

int main(){
freopen("3622.in","r",stdin);
freopen("3622.out","w",stdout);
scanf("%d %d",&n,&m);
if((n+m)&1){puts("0");return 0;}
m=n+m>>1;
C[0][0]=fac[0]=f[0][0]=1;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
sort(a+1,a+n+1);sort(b+1,b+n+1);
for(int i=1;i<=n;i++){
	fac[i]=fac[i-1]*i%P;
	C[i][0]=C[i][i]=1;
	for(int j=1;j<i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;
}
for(int i=1;i<=n;i++){
	while(k<n && a[i]>b[k+1])k++;f[i][0]=1;
	for(int j=0;j<=i;j++)f[i][j]=(f[i-1][j]+f[i-1][j-1]*max(k-j+1,0))%P;
}
for(int i=n;i>=m;i--){
	f[n][i]=f[n][i]*fac[n-i]%P;
	for(int j=i+1;j<=n;j++){
		f[n][i]-=f[n][j]*C[j][i];
		f[n][i]=(f[n][i]+P)%P;
	}
}
printf("%lld\n",f[n][m]);
return 0;
}

类似虚树的东西

首先我们发现答案就是当前存在的点所构成的树的边权和的两倍

所以我们考虑用set维护dfs序，最后减掉一个lca(最前,最后)即可

具体为什么是这样么……你需要自己手动模拟一下

非常妙

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;

const int N=100005;
const long long INF=21000000000000ll;

int n,m,en,h[N],dep[N],pos[N],f[N],lg[N<<1],tag[N],Index,Size;
long long ans,d[N<<1][19],di[N];
set<int> St;

struct Edge{
int b,next;
long long v;
}e[N<<1];

void dfs(int u){
d[pos[u]=++Index][0]=di[u];
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(dep[v])continue;
    f[v]=u;
    di[v]=di[u]+e[i].v;
    dep[v]=dep[u]+1;
    dfs(v);
    d[++Index][0]=di[u];
}
}

template<typename T>inline void Read(T &x){char ch;while((ch=getchar())<'0'||ch>'9');x=ch-'0';while((ch=getchar())>='0'&&ch<='9')x=x*10+ch-'0';}
void AddEdge(int sa,int sb,long long sc){e[++en].b=sb;e[en].v=sc;e[en].next=h[sa];h[sa]=en;}
set<int>::iterator Pre(const set<int>::iterator &x){set<int>::iterator Tx=x;return --Tx;}
set<int>::iterator Nxt(const set<int>::iterator &x){set<int>::iterator Tx=x;return ++Tx;}
long long Mn(int u,int v){int w=lg[v-u+1];return min(d[u][w],d[v-(1<<w)+1][w]);}
long long Dist(){if(!Size)return 0ll;int u=*St.begin(),v=*Pre(St.end());return Mn(u,v);}

void Ins(int x){
ans+=d[x][0];
St.insert(x);
Size++;
if(Size==1)return;
set<int>::iterator Tx=St.find(x);
if(Tx==St.begin()){ans-=Mn(*Tx,*Nxt(Tx));return;}
if(Nxt(Tx)==St.end()){ans-=Mn(*Pre(Tx),*Tx);return;}
ans+=Mn(*Pre(Tx),*Nxt(Tx))-Mn(*Tx,*Nxt(Tx))-Mn(*Pre(Tx),*Tx);
}

void Del(int x){
ans-=d[x][0];
if(Size==1){St.erase(x);Size--;return;}
set<int>::iterator Tx=St.find(x);
if(Tx==St.begin()){ans+=Mn(*Tx,*Nxt(Tx));St.erase(x);Size--;return;}
if(Nxt(Tx)==St.end()){ans+=Mn(*Pre(Tx),*Tx);St.erase(x);Size--;return;}
ans-=Mn(*Pre(Tx),*Nxt(Tx))-Mn(*Tx,*Nxt(Tx))-Mn(*Pre(Tx),*Tx);
St.erase(x);
Size--;
}

int main(){
freopen("3991.in","r",stdin);
freopen("3991.out","w",stdout);
Read(n);Read(m);
for(int i=1;i<n;i++){
    int u,v;
    long long w;
    Read(u);Read(v);Read(w);
    AddEdge(u,v,w);
	AddEdge(v,u,w);
}
dfs(1);
for(int i=2;i<=Index;i++)lg[i]=lg[i>>1]+1;
for(int i=1;i<=lg[Index];i++)for(int j=1;j+(1<<i)-1<=Index;j++)d[j][i]=min(d[j][i-1],d[j+(1<<i-1)][i-1]);
for(int i=1;i<=m;i++){
    int x;
    Read(x);
    tag[x]^=1;
    if(tag[x])Ins(pos[x]);
    else Del(pos[x]);
    printf("%lld\n",ans-Dist()<<1);
}
return 0;
}

有神犇@cooordi留言说我好多坑没填……

正好最近也颓废了几天了，不能再颓废了。

我明年还可以去NOI,机会还是有的

但是，不做题永远没有机会

必须填坑！

这篇博文用来记录我填好的坑。

2016/7/31 3:00

简易FFT教程 填坑完成

2016/8/1 21:30

更了一堆文章,好累(懒)啊明天再更

小伙伴们从四川回来了

5Au 4Ag 1Cu

lyz大爷高一随手Au，day2考246成功虐场

太强了%%%

而我在家连超哥线段树都不会（这两者有什么关系……）

还有好多坑没填

所以补一下

考虑标记永久化

计算断点位置对应的区间，确定怎么传标记

一开始我YY了一种写法，始终不过

后来发现情况少考虑了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=100005;

int n;
char s[10];
double ans;

struct SegTree{
int l,r;
double k,b;
inline double V(int x){return k*x+b;}
}tree[N<<2];

void Build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
tree[rt].k=tree[rt].b=0;
if(l==r)return;
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
}

double Cross(double k1,double b1,double k2,double b2){return (b2-b1)/(k1-k2);}

void Insert(int rt,double k,double b){
if(k*tree[rt].l+b<=tree[rt].V(tree[rt].l) && k*tree[rt].r+b<=tree[rt].V(tree[rt].r))return;
else if(k*tree[rt].l+b>=tree[rt].V(tree[rt].l) && k*tree[rt].r+b>=tree[rt].V(tree[rt].r)){tree[rt].k=k;tree[rt].b=b;return;}
int mid=tree[rt].l+tree[rt].r>>1;
double x=Cross(k,b,tree[rt].k,tree[rt].b);
if(k*tree[rt].l+b>=tree[rt].V(tree[rt].l)){
	if(x<=mid)Insert(rt<<1,k,b);
    else Insert(rt<<1|1,tree[rt].k,tree[rt].b),tree[rt].k=k,tree[rt].b=b;
}
else {
	if(x>mid)Insert(rt<<1|1,k,b);
    else Insert(rt<<1,tree[rt].k,tree[rt].b),tree[rt].k=k,tree[rt].b=b;
}
}

void Query(int rt,int x){
ans=max(ans,tree[rt].V(x));
if(tree[rt].l==tree[rt].r)return;
int mid=tree[rt].l+tree[rt].r>>1;
if(x<=mid)Query(rt<<1,x);
else Query(rt<<1|1,x);
}

int main(){
freopen("1568.in","r",stdin);
freopen("1568.out","w",stdout);
scanf("%d",&n);
Build(1,1,50000);
for(int i=1;i<=n;i++){
    scanf("%s",s);
    if(s[0]=='P'){double k,b;scanf("%lf %lf",&b,&k);Insert(1,k,b-k);}
    else {int x;scanf("%d",&x);ans=0;Query(1,x);printf("%lld\n",(long long)floor(ans/100.0));/*printf("%lf\n",ans);*/}
}
return 0;
}

先留下这个坑

这题我目前看到的有2种做法

做法1

做法2

占坑待填

教训：以后不能再取非常大的模数了，不然不好处理

最近因为某些原因没有更新博客……向还有在看我博客的人表示深深的歉意……

哈希，设dp[i][j]为第i个通配符的位置匹配了字符串前j位，转移基本是抄做法1的……

反正去不了绵阳了……

留下的好多的坑会一一填上。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005,M=15;
const long long P=1000000003ll,base=233ll;

bool f[M][N];
int n,len,pos[M],cnt;
long long Px[N]={1},ha1[N],ha2[N];
char s[N],str[N];

long long H1(int st,int ed){
if(st>ed)return 0ll;
return ((ha1[ed]-ha1[st-1]*Px[ed-st+1])%P+P)%P;
}

long long H2(int st,int ed){
if(st>ed)return 0ll;
return ((ha2[ed]-ha2[st-1]*Px[ed-st+1])%P+P)%P;
}

int main(){
freopen("3507.in","r",stdin);
freopen("3507.out","w",stdout);
scanf("%s",str+1);
len=strlen(str+1);
str[++len]='?';
for(int i=1;i<=len;i++)if(str[i]<'a' || str[i]>'z')pos[++cnt]=i;
for(int i=1;i<=len;i++)ha1[i]=ha1[i-1]*base%P+str[i];
for(int i=1;i<=100000;i++)Px[i]=Px[i-1]*base%P;
scanf("%d",&n);
while(n--){
	scanf("%s",s+1);
	len=strlen(s+1);
	s[++len]='#';
	for(int i=1;i<=len;i++)ha2[i]=ha2[i-1]*base%P+s[i];
    memset(f,0,sizeof(f));
    f[0][0]=1;
    for(int i=0;i<cnt;i++){
		if(str[pos[i]]=='*')for(int j=1;j<=len;j++)if(f[i][j-1])f[i][j]=1;
		for(int j=0;j<=len;j++){
            //printf("Ha1[%d,%d]=%lld , Ha2[%d,%d]=%lld\n",pos[i]+1,pos[i+1]-1,H1(pos[i]+1,pos[i+1]-1),j+1,j+pos[i+1]-pos[i]-1,H2(j+1,j+pos[i+1]-pos[i]-1));
			if(f[i][j]&&H1(pos[i]+1,pos[i+1]-1)==H2(j+1,j+pos[i+1]-pos[i]-1)){
				if(str[pos[i+1]]=='?')f[i+1][j+pos[i+1]-pos[i]]=1;
                else f[i+1][j+pos[i+1]-pos[i]-1]=1;
			}
		}
    }
    puts(f[cnt][len]?"YES":"NO");
}
return 0;
}

这是一篇简易的FFT教程，作者水平奇低无比，这篇博文仅仅是用于分享体会

已经学会FFT的神犇们可以直接无视这篇文章

推荐几个学习FFT的很好的博客地址:Picks大神的博客 Miskcoo大神的博客 FFT算法学习笔记 （对于想要进阶的来说去第一个，基础去第二个，入门去第三个）

我觉得学FFT先要去看上面三个博客，实在一点看不懂在看我的口胡……

而且我的口胡非常模糊(半夜三点在写这东西)，难免会出错，敬请指正~

嗯，蒟蒻Lvat_s开始口胡了

首先你需要知道什么是FFT

其实我也不知道是啥，但是有个专业的名字叫做Fast Fourier Transform(快速傅立叶变换)

相信看这篇博文的神犇们都具有初中数学姿势:一个二次函数可以被三个点表示出来

而小学数学告诉我们一个一次函数可以用两个点表示出来

所以，我们类比一下，一个n次多项式$F(n)=a_n*x^n+......+a_1*x+a_0$可以用n+1个二维平面上的点来表示，这些点称为多项式的点值表示法

我们再来思考一下函数是怎么乘起来的

例如$F*G=......$(懒得写了)(总之就是对于x坐标相同的点，将两个函数的y坐标值相乘后就行了)

那么对于点值表达我们可以$O(n)$的实现乘法

所以离散傅立叶变换(DFT)就是暴力的将这些点分拆与合并，时间复杂度$O(n^2)$

为什么DFT复杂度这么高？

都是开始分拆多项式和后期合并的锅!

初中数学告诉我们由一个二次函数得到的三个点不具有唯一性，而由三个点合成的那个二次函数一定是唯一的

我们再来类比一下就知道了n次多项式$F(n)$也可以这么做

所以，FFT就是找一些合适的点用$O(nlog_2n)$得到点值表达，然后$O(n)$计算乘法，最后用$O(nlog_2n)$来重新得到这个多项式。

然而怎么降低复杂度呢？

我们选择单位复数根的倍数作为我们要找的这些点的x坐标。

看起来好像一点用没有……真的没有吗？

当然是有用的了。

（未完待续）

更新啦

我们需要知道关于复数的两个引理

设$w_n=e^{2\pi/n}$

消去引理:$w_{dk}^{dk}=w_k^k(n>=0,k>=0,d>=0)$证明很简单，带进去算下就行= =

折半引理:我不太会Mathjax语法怎么办……那就弄个图片吧

还有一个求和引理就不发了= =懒得截图了

这三个引理使我们可以证明FFT的正确性。

FFT的核心就是分组(按照奇数和偶数对多项式的指数进行分组)。

如果我们可以在单次$O(n)$时间内合并($n$为多项式的长度)，那么多项式乘法就可以在$O(nlogn)$的时间内解决。

事实是确实可以这样

具体证明在我推荐的第三个博客地址里面就有，讲的还是很清晰的。

那么我们就可以递归FFT啦！

当然这样不优美。

我们可以改成非递归版的，这样节省时间。

写的好渣啊……主要是因为当初看了好多FFT方面的博客都看不懂，所以才决定事无巨细的写这篇文章。

====================分割线=======================

多项式求逆

这玩意要用到类似倍增的东西，我还没想太清楚……

过几天更新

orz rky大爷几个月前就会了

随机化乱搞

学习了一下bitset怎么用感觉不错

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<bitset>
#include<algorithm>
using namespace std;
 
const int N=105;
typedef bitset<N> Bt;
 
int n,d,ord[N],CNT=1000;
Bt A[N],nw,ans,can;
 
struct Point{
int x,y;
}poi[N];
 
int Sqr(int x){return x*x;}
int Dist(Point A,Point B){return Sqr(A.x-B.x)+Sqr(A.y-B.y);}
 
int main(){
freopen("4080.in","r",stdin);
freopen("4080.out","w",stdout);
scanf("%d %d",&n,&d);
for(int i=1;i<=n;i++)scanf("%d %d",&poi[i].x,&poi[i].y);
for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
        if(Dist(poi[i],poi[j])<=d*d)A[i].set(j),A[j].set(i);
    }
}
for(int i=1;i<=n;i++)ord[i]=i;
while(CNT--){
    can.set();
    nw.reset();
    for(int i=1;i<=n;i++){
        if(can.test(ord[i])){
            nw.set(ord[i]);
            can&=A[ord[i]];
        }
    }
    if(nw.count()>ans.count())ans=nw;
    random_shuffle(ord+1,ord+n+1);
}
printf("%d\n",ans.count());
for(int i=1;i<=n;i++)if(ans.test(i))printf("%d ",i);
return 0;
}

和我做过的另外一个BZOJ题很像，但是忘了题号了……BZOJ3306 题解

换根就是针对当前根找到子树然后容斥一下

注意dfs序中一棵树的子树一定是连续的

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N=100005;
 
int n,m,a[N],id[N],pre[N],segn,en,h[N],root,siz[N],son[N],dep[N],fa[N],top[N],OPTION;
 
struct Edge{
int b,next;
}e[N<<1];
 
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
 
struct SegTree{
int l,r,mn,tag;
}tree[N<<2];
 
void Pushdown(int rt){
if(tree[rt].tag){
    tree[rt<<1].tag=tree[rt].tag;
    tree[rt<<1|1].tag=tree[rt].tag;
    tree[rt<<1].mn=tree[rt].tag;
    tree[rt<<1|1].mn=tree[rt].tag;
    tree[rt].tag=0;
}
}
 
void Pushup(int rt){
tree[rt].mn=min(tree[rt<<1].mn,tree[rt<<1|1].mn);
}
 
void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r){tree[rt].mn=a[pre[l]];return;}
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
Pushup(rt);
}
 
void Modify(int rt,int l,int r,int x){
if(l<=tree[rt].l && tree[rt].r<=r){tree[rt].mn=x;tree[rt].tag=x;return;}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Modify(rt<<1,l,r,x);
if(r>mid)Modify(rt<<1|1,l,r,x);
Pushup(rt);
}
 
int Query(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r)return tree[rt].mn;
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(r<=mid)return Query(rt<<1,l,r);
else if(l>mid)return Query(rt<<1|1,l,r);
else return min(Query(rt<<1,l,r),Query(rt<<1|1,l,r));
}
 
void dfs1(int u,int fat){
siz[u]=1;
dep[u]=dep[fat]+1;
son[u]=0;
fa[u]=fat;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fat)continue;
    dfs1(v,u);
    siz[u]+=siz[v];
    if(siz[v]>siz[son[u]])son[u]=v;
}
}
 
void dfs2(int u,int ux){
top[u]=ux;
id[u]=++segn;
pre[segn]=u;
if(son[u])dfs2(son[u],ux);
else return;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(son[u]==v || fa[u]==v)continue;
    dfs2(v,v);
}
}
 
void Change(int x,int y,int v){
int topx=top[x],topy=top[y];
while(topx!=topy){
    if(dep[topx]<dep[topy]){swap(topx,topy);swap(x,y);}
    Modify(1,id[topx],id[x],v);
    x=fa[topx];
    topx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
Modify(1,id[x],id[y],v);
}
 
int Ask(int Id){
if(root==Id)return Query(1,1,n);
int x=root,y=Id,topx=top[x],topy=top[y];
while(topx!=topy){
    if(dep[topx]<dep[topy]){swap(topx,topy);swap(x,y);}
    x=fa[topx];
    topx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
if(x!=Id)return Query(1,id[Id],id[Id]+siz[Id]-1);
else {
    for(int i=h[Id];i;i=e[i].next){
        int v=e[i].b;
        if(fa[Id]==v)continue;
        if(id[v]<=id[root] && id[root]<=id[v]+siz[v]-1){
            int mn=Query(1,id[1],id[v]-1);
            if(id[v]+siz[v]-1!=n)mn=min(mn,Query(1,id[v]+siz[v],n));
            return mn;
        }
    }
}
}
 
void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}
 
int main(){
freopen("3083.in","r",stdin);
freopen("3083.out","w",stdout);
Read(n);Read(m);
for(int i=1;i<n;i++){int u,v;Read(u);Read(v);AddEdge(u,v);AddEdge(v,u);}
for(int i=1;i<=n;i++)Read(a[i]);
Read(root);
dfs1(1,0);
dfs2(1,1);
Build(1,1,n);
while(m--){
    int opt,x,y,v;
    Read(opt);
    if(opt==1){Read(x);root=x;}
    if(opt==2){Read(x);Read(y);Read(v);Change(x,y,v);}
    if(opt==3){Read(x);printf("%d\n",Ask(x));}
}
return 0;
}

最小生成树弄出来倍增就没了

和NOIP的货车运输没什么区别

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N=15005;
 
int n,m,f[N],k,cnt,dep[N],fa[N][15],V[N][15],en,h[N];
 
struct Ed{
int a,b,v;
friend bool operator<(Ed A,Ed B){return A.v<B.v;}
}es[N<<1];
 
struct Edge{
int b,v,next;
}e[N<<1];
 
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
 
int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
 
int LCA(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int deep=dep[u]-dep[v],Mx=-1;
for(int i=0;i<=14;i++)if(deep&(1<<i)){Mx=max(Mx,V[u][i]);u=fa[u][i];}
for(int i=14;i>=0;i--){
    if(fa[u][i]!=fa[v][i]){Mx=max(Mx,max(V[u][i],V[v][i]));u=fa[u][i];v=fa[v][i];}
}
return u==v?Mx:max(Mx,max(V[u][0],V[v][0]));
}
 
void Prepare(){
for(int i=1;i<=14;i++){
    for(int j=1;j<=n;j++){
        fa[j][i]=fa[fa[j][i-1]][i-1];
        V[j][i]=max(V[j][i-1],V[fa[j][i-1]][i-1]);
    }
}
}
 
void dfs(int u,int fat){
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fat)continue;
    fa[v][0]=u;
    dep[v]=dep[u]+1;
    V[v][0]=e[i].v;
    dfs(v,u);
}
}
 
int main(){
freopen("3732.in","r",stdin);
freopen("3732.out","w",stdout);
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)scanf("%d %d %d",&es[i].a,&es[i].b,&es[i].v);
sort(es+1,es+m+1);
for(int i=1;i<=m && cnt<n-1;i++){
    if(Find(es[i].a)!=Find(es[i].b)){
        AddEdge(es[i].a,es[i].b,es[i].v);
        AddEdge(es[i].b,es[i].a,es[i].v);
        cnt++;
        f[Find(es[i].a)]=Find(es[i].b);
    }
}
dfs(1,0);
Prepare();
for(int i=1;i<=k;i++){
    int u,v;
    scanf("%d %d",&u,&v);
    printf("%d\n",LCA(u,v));
}
return 0;
}

嗯……

因为每次加上的d都是正值，那么最多只有n次从负数到非负数的转换

所以我们分正负数分别维护，统计贡献时加一加就好了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
 
const int N=100005;
const long long INF=999999999999999ll;
 
int n,m,dep[N],siz[N],son[N],fa[N],id[N],pre[N],segn,en,h[N],top[N];
long long a[N];
 
struct Edge{
int b,next;
}e[N<<1];
 
void AddEdge(int sa,int sb){e[++en].b=sb;e[en].next=h[sa];h[sa]=en;}
 
struct SegTree{
int l,r;
long long s1,s2,tag,mx,sn1,sn2,sum;
}tree[N<<2];
 
void Pushdown(int rt){
if(tree[rt].tag){
    tree[rt<<1].tag+=tree[rt].tag;
    tree[rt<<1].s1+=tree[rt<<1].sn1*tree[rt].tag;
    tree[rt<<1].s2+=tree[rt<<1].sn2*tree[rt].tag;
    tree[rt<<1].sum=tree[rt<<1].s1-tree[rt<<1].s2;
    tree[rt<<1].mx+=tree[rt].tag;
    tree[rt<<1|1].tag+=tree[rt].tag;
    tree[rt<<1|1].s1+=tree[rt<<1|1].sn1*tree[rt].tag;
    tree[rt<<1|1].s2+=tree[rt<<1|1].sn2*tree[rt].tag;
    tree[rt<<1|1].sum=tree[rt<<1|1].s1-tree[rt<<1|1].s2;
    tree[rt<<1|1].mx+=tree[rt].tag;
    tree[rt].tag=0;
}
}
 
void Pushup(int rt){
tree[rt].mx=max(tree[rt<<1].mx,tree[rt<<1|1].mx);
tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
tree[rt].sn1=tree[rt<<1].sn1+tree[rt<<1|1].sn1;
tree[rt].sn2=tree[rt<<1].sn2+tree[rt<<1|1].sn2;
tree[rt].s1=tree[rt<<1].s1+tree[rt<<1|1].s1;
tree[rt].s2=tree[rt<<1].s2+tree[rt<<1|1].s2;
}
 
void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r){
    if(a[pre[l]]>=0){
        tree[rt].s1+=a[pre[l]];
        tree[rt].sn1=1;
        tree[rt].mx=-INF;
    }
    else {
        tree[rt].s2+=a[pre[l]];
        tree[rt].sn2=1;
        tree[rt].mx=a[pre[l]];
    }
    tree[rt].sum=tree[rt].s1-tree[rt].s2;
    return;
}
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
Pushup(rt);
}
 
void Ex_Modify(int rt,int d){
if(tree[rt].l==tree[rt].r){
    tree[rt].sn1=1;
    tree[rt].sn2=0;
    tree[rt].s1=tree[rt].s2+d;
    tree[rt].s2=0;
    tree[rt].mx=-INF;
    tree[rt].sum=tree[rt].s1;
    return;
}
Pushdown(rt);
if(tree[rt<<1].mx+d>0)Ex_Modify(rt<<1,d);
else {
    tree[rt<<1].tag+=d;
    tree[rt<<1].s1+=tree[rt<<1].sn1*d;
    tree[rt<<1].s2+=tree[rt<<1].sn2*d;
    tree[rt<<1].sum=tree[rt<<1].s1-tree[rt<<1].s2;
    tree[rt<<1].mx+=d;
}
if(tree[rt<<1|1].mx+d>0)Ex_Modify(rt<<1|1,d);
else {
    tree[rt<<1|1].tag+=d;
    tree[rt<<1|1].s1+=tree[rt<<1|1].sn1*d;
    tree[rt<<1|1].s2+=tree[rt<<1|1].sn2*d;
    tree[rt<<1|1].sum=tree[rt<<1|1].s1-tree[rt<<1|1].s2;
    tree[rt<<1|1].mx+=d;
}
Pushup(rt);
}
 
void Modify(int rt,int l,int r,long long d){
if(l<=tree[rt].l && tree[rt].r<=r){
    if(tree[rt].mx+d>0){Ex_Modify(rt,d);}
    else {tree[rt].tag+=d;tree[rt].mx+=d;tree[rt].s1+=d*tree[rt].sn1;tree[rt].s2+=d*tree[rt].sn2;tree[rt].sum=tree[rt].s1-tree[rt].s2;}
    return;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Modify(rt<<1,l,r,d);
if(r>mid)Modify(rt<<1|1,l,r,d);
Pushup(rt);
}
 
long long Query(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r)return tree[rt].sum;
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(r<=mid)return Query(rt<<1,l,r);
else if(l>mid)return Query(rt<<1|1,l,r);
else return Query(rt<<1,l,r)+Query(rt<<1|1,l,r);
}
 
void dfs1(int u,int fat){
dep[u]=dep[fat]+1;
fa[u]=fat;
siz[u]=1;
son[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fat)continue;
    dfs1(v,u);
    siz[u]+=siz[v];
    if(siz[v]>siz[son[u]])son[u]=v;
}
}
 
void dfs2(int u,int ux){
top[u]=ux;
id[u]=++segn;
pre[segn]=u;
if(son[u])dfs2(son[u],ux);
else return;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fa[u] || v==son[u])continue;
    dfs2(v,v);
}
}
 
void Update(int u,int v,long long d){
int topu=top[u],topv=top[v];
while(topu!=topv){
    if(dep[topu]<dep[topv]){swap(topu,topv);swap(u,v);}
    Modify(1,id[topu],id[u],d);
    u=fa[topu];
    topu=top[u];
}
if(dep[u]>dep[v])swap(u,v);
Modify(1,id[u],id[v],d);
}
 
long long Ask(int u,int v){
int topu=top[u],topv=top[v];
long long Sum=0;
while(topu!=topv){
    if(dep[topu]<dep[topv]){swap(topu,topv);swap(u,v);}
    Sum+=Query(1,id[topu],id[u]);
    u=fa[topu];
    topu=top[u];
}
if(dep[u]>dep[v])swap(u,v);
return Sum+Query(1,id[u],id[v]);
}
 
int main(){
freopen("4127.in","r",stdin);
freopen("4127.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<n;i++){
    int u,v;
    scanf("%d %d",&u,&v);
    AddEdge(u,v);
    AddEdge(v,u);
}
dfs1(1,0);
dfs2(1,1);
Build(1,1,n);
while(m--){
    int opt,u,v;
    long long d;
    scanf("%d %d %d",&opt,&u,&v);
    if(opt==1){scanf("%lld",&d);Update(u,v,d);}
    if(opt==2)printf("%lld\n",Ask(u,v));
}
return 0;
}