一棵树，有点权和边权。
你需要对这棵树进行操作，每次选择一条路径，代价为路径两端的点权和，将路径上的边权全部减一。
问最小代价。
支持路径边权加操作。
(nle 2*10^5,Qle 2*10^5)
dyp对NOIP2018D1T1的魔改。
%%%dyp
考虑一个节点的贡献。那么相当于这样的问题：一堆数(a_i)，每次选择(x eq y,a_x,a_y>0)，将(a_x,a_y)分别减一。问最后剩下的数最少是多少。
结论：如果(2max a_i> sum a_i)，则答案为(2max a_i -sum a_i)。否则为(sum a_imod 2)。
证明考虑假设操作到最后只剩(a_i)，假设(a_ige 2)，如果在之前的操作中，存在((a_j,a_k))，那么调整成((a_j,a_i),(a_k,a_i))显然更优，所以前面的操作都是((a_x,a_i))的形式。在这种情况下，(a_i)取一开始的最大值是最优的，此时满足(2max a_i -sum a_i>0)。如果不满足，那么最后操作剩下的数根据总和的奇偶性判定。
如果(sum a_imod 2=1)，不妨一开始给(max a_i)减一。然后后面再进行判断。
于是贡献为：(max(2max a_i-sum a_i,0)*w)。
对于一次修改，两端的点暴力做，考虑中间的点：如果改的两条边中，其中一条为过半边，此时(2(a_i+Delta)-(sum a_i+2Delta)>0)，贡献不变；如果两条都不是过半边，那么贡献减(2Delta)，和(0)取(max)。
那么可以发现：对于中间的点，贡献是递减的，除非它成为了一次修改的端点，否则它的贡献不可能增加。于是可以找到即将变成(0)的贡献，暴力修改。一次修改操作多(2)的势能，所以总势能为(O(n+q))。
总结一下：先发现结论，然后分开处理端点和中间的点，中间的点可以快速改；端点增加势能，中间的点减势能，时间复杂度是对的。
后面要做的就是树剖维护这个东西，按套路搞即可，不再赘述。
因为懒得写所以把std贴在这里。
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define maxn 200005
#define inf 1e18
#define ll long long
using namespace std;
int n,q,i,j,k,fai[maxn];
int em,e[maxn*2],nx[maxn*2],ls[maxn],ec[maxn*2];
ll w[maxn];
void read(int &x){
x=0; char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar());
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
}
void insert(int x,int y,int z){
em++; e[em]=y; nx[em]=ls[x]; ls[x]=em; ec[em]=z;
em++; e[em]=x; nx[em]=ls[y]; ls[y]=em; ec[em]=z;
}
//shu pou
int tot,dfn[maxn],Idfn[maxn],sz[maxn],g[maxn],top[maxn],dep[maxn],fa[maxn];
void dfs(int x,int p){
dep[x]=dep[p]+1,sz[x]=1,fa[x]=p;
for(int i=ls[x];i;i=nx[i]) if (e[i]!=p){
fai[e[i]]=i,dfs(e[i],x),sz[x]+=sz[e[i]];
if (sz[e[i]]>sz[g[x]]) g[x]=e[i];
}
}
void dfs2(int x,int p){
dfn[x]=++tot,Idfn[tot]=x;
if (x==1) top[x]=x;
if (g[x]) top[g[x]]=top[x],dfs2(g[x],x);
for(int i=ls[x];i;i=nx[i]) if (e[i]!=p&&e[i]!=g[x])
top[e[i]]=e[i],dfs2(e[i],x);
}
int getlca(int x,int y){
while (top[x]!=top[y]){
if (dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return (dep[x]<dep[y])?x:y;
}
// yu chu li
ll sum[maxn],v[maxn],ans; int p[maxn];
void prepare(){
for(int x=1;x<=n;x++) {
for(int i=ls[x];i;i=nx[i]) sum[x]+=ec[i];
for(int i=ls[x];i;i=nx[i]) if (2*ec[i]>sum[x]+(sum[x]&1))
p[x]=i;
ans+=w[x]*(sum[x]&1);
if (p[x]) {
if (e[p[x]]!=fa[x]&&e[p[x]]!=g[x])
v[x]=2*ec[p[x]]-sum[x]-(sum[x]&1);
else v[x]=inf;
ans+=w[x]*(2*ec[p[x]]-sum[x]-(sum[x]&1));
p[x]=e[p[x]];
} else v[x]=inf;
}
}
// sum
struct Treearray{
ll s[maxn];
void add(int x,ll d){for(;x<=n;x+=x&-x) s[x]+=d;}
ll sum(int x,ll S=0){for(;x;x-=x&-x) S+=s[x];return S;}
ll query(int l,int r){return sum(r)-sum(l-1);}
} T1,T2;
void addchain(int x,int y,int z,int d){
if (x==y) return;
T1.add(dfn[x],d),T1.add(dfn[y],d),T1.add(dfn[z],-2*d);
if (dep[x]<dep[y]) swap(x,y);
if (y==z) {
sum[x]+=d,sum[y]+=d;
if (fa[x]!=y)
T2.add(dfn[fa[x]],2*d),T2.add(dfn[y],-2*d);
} else {
sum[x]+=d,sum[y]+=d;
x=fa[x],y=fa[y];
T2.add(dfn[x],2*d),T2.add(dfn[y],2*d);
T2.add(dfn[z],-2*d);
if (fa[z]) T2.add(dfn[fa[z]],-2*d);
}
}
ll gete(int x){
return ec[fai[x]]+T1.query(dfn[x],dfn[x]+sz[x]-1);
}
ll gets(int x){return sum[x]+T2.query(dfn[x],dfn[x]+sz[x]-1);}
//segment tree
ll t[maxn*4],tag[maxn*4],ts[maxn*4];
void upd(int x){t[x]=min(t[x<<1]+tag[x<<1],t[x<<1^1]+tag[x<<1^1]),ts[x]=ts[x<<1]+ts[x<<1^1];}
void downtag(int x,int l,int r){
t[x]+=tag[x];
if (l<r) tag[x<<1]+=tag[x],tag[x<<1^1]+=tag[x];
tag[x]=0;
}
void maketree(int x,int l,int r){
if (l==r) {
t[x]=v[Idfn[l]];
ts[x]=(t[x]>1e17)?0:w[Idfn[l]];
return;
}
int mid=(l+r)>>1;
maketree(x<<1,l,mid),maketree(x<<1^1,mid+1,r);
upd(x);
}
void cover(int x,int l,int r,int d){
if (tag[x]) downtag(x,l,r);
if (t[x]-d>0) return;
if (l==r){
p[Idfn[l]]=0;
ans-=t[x]*w[Idfn[l]],t[x]=inf,ts[x]=0;
return;
}
int mid=(l+r)>>1;
cover(x<<1,l,mid,d),cover(x<<1^1,mid+1,r,d);
upd(x);
}
void add(int x,int l,int r,int L,int R,int d){
if (tag[x]) downtag(x,l,r);
if (l>R||r<L) return;
if (L<=l&&r<=R) {
cover(x,l,r,d);
ans-=ts[x]*d,tag[x]-=d;
downtag(x,l,r);
return;
}
int mid=(l+r)>>1;
add(x<<1,l,mid,L,R,d),add(x<<1^1,mid+1,r,L,R,d);
upd(x);
}
void clear(int x,int l,int r,int v){
if (tag[x]) downtag(x,l,r);
if (l==r){
ans-=t[x]*w[Idfn[v]],t[x]=inf,ts[x]=0;
return;
}
int mid=(l+r)>>1;
if (v<=mid) clear(x<<1,l,mid,v);
else clear(x<<1^1,mid+1,r,v);
upd(x);
}
void addit(int x,int l,int r,int v,ll s){
if (tag[x]) downtag(x,l,r);
if (l==r){
t[x]=s,ts[x]=w[Idfn[v]];
return;
}
int mid=(l+r)>>1;
if (v<=mid) addit(x<<1,l,mid,v,s);
else addit(x<<1^1,mid+1,r,v,s);
upd(x);
}
void check(int x,int y,int d){
ll tmp1=gete(y),tmp2=gets(x);
if (tmp1*2-tmp2-(tmp2&1)-d*2<=0)
ans-=(tmp1*2-tmp2-(tmp2&1))*w[x],p[x]=0;
else ans-=2ll*d*w[x];
}
ll getit(int x,int l,int r,int v){
if (tag[x]) downtag(x,l,r);
if (l==r) return t[x];
int mid=(l+r)>>1;
if (v<=mid) return getit(x<<1,l,mid,v);
else return getit(x<<1^1,mid+1,r,v);
}
void doit(int x,int z,int d){
while (top[x]!=top[z]){
if (top[x]!=x)
add(1,1,n,dfn[top[x]],dfn[x]-1,d*2);
x=top[x];
if (fa[x]==z) return;
int y=fa[x];
if (p[y]&&p[y]!=fa[y]&&p[y]!=x){
if (p[y]!=g[y]) add(1,1,n,dfn[y],dfn[y],d*2);
else check(y,p[y],d);
}
x=fa[x];
}
if (dfn[z]+1<dfn[x])
add(1,1,n,dfn[z]+1,dfn[x]-1,d*2);
}
void doitlca(int z,int x,int y,int d){
if (!p[z]) return;
k=p[z];
if (k==fa[z]) {check(z,z,d);return;}
if (dfn[k]<=dfn[x]&&dfn[x]<dfn[k]+sz[k]) return;
if (dfn[k]<=dfn[y]&&dfn[y]<dfn[k]+sz[k]) return;
if (k!=g[z]) add(1,1,n,dfn[z],dfn[z],d*2);
else check(z,k,d);
}
int jump(int x,int y){
x=top[x];
while (top[fa[x]]!=top[y]) x=top[fa[x]];
return x;
}
void doitpoint(int x,int y,int z,int d){
if (x==z){
if (dfn[g[x]]<=dfn[y]&&dfn[y]<dfn[g[x]]+sz[g[x]]) k=g[x];
else k=jump(y,x);
} else k=fa[x];
if (p[x]){
if (p[x]!=fa[x]&&p[x]!=g[x])
clear(1,1,n,dfn[x]);
else {
ll tmp1=gete((p[x]==fa[x])?x:p[x]),tmp2=gets(x);
ans-=(tmp1*2-tmp2-(tmp2&1))*w[x];
}
}
ans-=(sum[x]&1)*w[x];
ll tmp,tmp0=gete((k==fa[x])?x:k)+d,s;
if (p[x]) {
tmp=gete((p[x]==fa[x])?x:p[x]);
if (tmp>tmp0) s=p[x]; else s=k,tmp=tmp0;
} else s=k,tmp=tmp0;
ll sum0=gets(x)+d; ans+=(sum0&1)*w[x];
if (tmp*2-sum0-(sum0&1)>0){
p[x]=s,ans+=(tmp*2-sum0-(sum0&1))*w[x];
if (s!=fa[x]&&s!=g[x])
addit(1,1,n,dfn[x],tmp*2-sum0-(sum0&1));
} else p[x]=0;
}
int main(){
freopen("snow.in","r",stdin);
freopen("snow.out","w",stdout);
read(n),read(q);
for(i=1;i<=n;i++) read(k),w[i]=k;
for(i=1;i<n;i++){
int x,y,z; read(x),read(y),read(z);
insert(x,y,z);
}
dfs(1,0),dfs2(1,0);
prepare();
printf("%lld
",ans);
maketree(1,1,n);
while (q--){
int x,y,z,d; read(x),read(y),read(d);
z=getlca(x,y);
if (x!=z) doit(x,z,d);
if (y!=z) doit(y,z,d);
if (z!=x&&z!=y) doitlca(z,x,y,d);
doitpoint(x,y,z,d);
doitpoint(y,x,z,d);
addchain(x,y,z,d);
printf("%lld
",ans);
}
}