#pragma GCC optimize(3)
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const ll INF=1e11;
int Head[N],Next[N<<1],vet[N<<1];
int top[N],fa[N],ch[N][2],son[N],sz[N],lsz[N],stk[N],Fa[N],pre[N];
ll dp[N][2],g[N][2],p[N];
int n,m,u,v,edgenum,a,x,b,y,root,cnt;
char s[10];
inline ll Min(const ll& a, const ll& b){ return a<b?a:b; }
struct Matrix{ ll a[2][2]; };
inline Matrix Get(const ll& x, const ll& y){
Matrix c;
c.a[0][0]=INF; c.a[0][1]=x;
c.a[1][0]=c.a[1][1]=y;
return c;
}
Matrix tree[N],Node[N];
Matrix operator * (const Matrix& a, const Matrix& b){
Matrix c;
c.a[0][0]=Min(a.a[0][0]+b.a[0][0],a.a[0][1]+b.a[1][0]);
c.a[0][1]=Min(a.a[0][0]+b.a[0][1],a.a[0][1]+b.a[1][1]);
c.a[1][0]=Min(a.a[1][0]+b.a[0][0],a.a[1][1]+b.a[1][0]);
c.a[1][1]=Min(a.a[1][0]+b.a[0][1],a.a[1][1]+b.a[1][1]);
return c;
}
inline void addedge(const int& u, const int& v){
vet[++edgenum]=v;
Next[edgenum]=Head[u];
Head[u]=edgenum;
}
inline void pushup(const int& u){ tree[u]=tree[ch[u][0]]*Node[u]*tree[ch[u][1]]; }
inline void update(int u){
Node[u]=Get(g[u][0],g[u][1]);
for (; u; u=fa[u]){
int f=fa[u];
if (f && ch[f][0]!=u && ch[f][1]!=u){
g[f][0]-=tree[u].a[1][1]; g[f][1]-=Min(tree[u].a[0][1],tree[u].a[1][1]);
pushup(u);
g[f][0]+=tree[u].a[1][1]; g[f][1]+=Min(tree[u].a[0][1],tree[u].a[1][1]);
Node[f]=Get(g[f][0],g[f][1]);
} else pushup(u);
}
}
int build(int l, int r){
if (l>r) return 0;
int hav=(pre[r]+pre[l-1]+1)/2;
int k=lower_bound(pre+l,pre+r+1,hav)-pre,u=stk[k];
fa[ch[u][0]=build(l,k-1)]=u;
fa[ch[u][1]=build(k+1,r)]=u;
pushup(u); return u;
}
void dfs1(const int& u, const int& f){
sz[u]=1; dp[u][1]=p[u]; fa[u]=Fa[u]=f;
for (int e=Head[u]; e; e=Next[e]){
int v=vet[e];
if (v==f) continue;
dfs1(v,u); sz[u]+=sz[v];
dp[u][0]+=dp[v][1];
dp[u][1]+=Min(dp[v][0],dp[v][1]);
if (sz[v]>sz[son[u]]) son[u]=v;
}
lsz[u]=sz[u]-sz[son[u]];
}
void dfs2(const int& u, const int& f, const int& st){
top[u]=st; g[u][1]=p[u];
if (son[u]) dfs2(son[u],u,st);
for (int e=Head[u]; e; e=Next[e]){
int v=vet[e];
if (v==son[u] || v==f) continue;
dfs2(v,u,v);
g[u][0]+=dp[v][1];
g[u][1]+=Min(dp[v][0],dp[v][1]);
}
Node[u]=Get(g[u][0],g[u][1]);
if (top[u]==u){
cnt=0;
for (int i=u; i; i=son[i]) stk[++cnt]=i,pre[cnt]=pre[cnt-1]+lsz[i];
int las=fa[u];
fa[root=build(1,cnt)]=las;
}
}
inline int read(){
int num=0,fu=1; char ch=getchar();
while (ch<'0' || ch>'9'){ if (ch=='-') fu=0; ch=getchar(); }
while (ch>='0' && ch<='9'){ num=(num<<3)+(num<<1)+ch-'0'; ch=getchar(); }
return fu?num:-num;
}
int main(){
freopen("defense.in","r",stdin);
freopen("defense.out","w",stdout);
n=read(); m=read(); scanf("%s",s);
ll *P=p;
for (register int i=1; i<=n; i++) *(P+i)=read();
for (register int i=1; i<n; i++){
u=read(); v=read();
addedge(u,v); addedge(v,u);
}
tree[0].a[0][0]=tree[0].a[1][1]=0;
tree[0].a[0][1]=tree[0].a[1][0]=INF;
dfs1(1,0); dfs2(1,0,1);
for (; m; m--){
a=read(); x=read(); b=read(); y=read();
if (!x && !y && (Fa[a]==b || Fa[b]==a)){ puts("-1"); continue; }
x^=1; y^=1;
ll last1=g[a][x],last2=g[b][y];
g[a][x]=INF; update(a);
g[b][y]=INF; update(b);
printf("%lld\n",Min(tree[root].a[0][1],tree[root].a[1][1]));
g[a][x]=last1; update(a);
g[b][y]=last2; update(b);
}
return 0;
}
/*
5 3 C3
2 4 1 3 9
1 5
5 2
5 3
3 4
1 0 3 0
2 1 3 1
1 0 5 0
*/
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 23.65 us | 84 KB | Accepted | Score: 4 | 显示更多 |
Testcase #2 | 28.38 us | 84 KB | Accepted | Score: 4 | 显示更多 |
Testcase #3 | 28.07 us | 84 KB | Accepted | Score: 4 | 显示更多 |
Testcase #4 | 22.79 us | 84 KB | Accepted | Score: 4 | 显示更多 |
Testcase #5 | 118.64 us | 116 KB | Accepted | Score: 4 | 显示更多 |
Testcase #6 | 116.64 us | 116 KB | Accepted | Score: 4 | 显示更多 |
Testcase #7 | 118.43 us | 108 KB | Accepted | Score: 4 | 显示更多 |
Testcase #8 | 1.579 ms | 788 KB | Accepted | Score: 4 | 显示更多 |
Testcase #9 | 1.689 ms | 788 KB | Accepted | Score: 4 | 显示更多 |
Testcase #10 | 1.506 ms | 576 KB | Accepted | Score: 4 | 显示更多 |
Testcase #11 | 1.505 ms | 576 KB | Accepted | Score: 4 | 显示更多 |
Testcase #12 | 114.223 ms | 35 MB + 12 KB | Accepted | Score: 4 | 显示更多 |
Testcase #13 | 114.041 ms | 35 MB + 12 KB | Accepted | Score: 4 | 显示更多 |
Testcase #14 | 99.059 ms | 34 MB + 840 KB | Accepted | Score: 4 | 显示更多 |
Testcase #15 | 99.694 ms | 34 MB + 844 KB | Accepted | Score: 4 | 显示更多 |
Testcase #16 | 99.761 ms | 34 MB + 844 KB | Accepted | Score: 4 | 显示更多 |
Testcase #17 | 139.697 ms | 35 MB + 12 KB | Accepted | Score: 4 | 显示更多 |
Testcase #18 | 65.926 ms | 15 MB + 968 KB | Accepted | Score: 4 | 显示更多 |
Testcase #19 | 65.913 ms | 15 MB + 968 KB | Accepted | Score: 4 | 显示更多 |
Testcase #20 | 89.575 ms | 24 MB + 512 KB | Accepted | Score: 4 | 显示更多 |
Testcase #21 | 89.561 ms | 24 MB + 508 KB | Accepted | Score: 4 | 显示更多 |
Testcase #22 | 90.194 ms | 24 MB + 316 KB | Accepted | Score: 4 | 显示更多 |
Testcase #23 | 126.606 ms | 24 MB + 496 KB | Accepted | Score: 4 | 显示更多 |
Testcase #24 | 126.806 ms | 24 MB + 512 KB | Accepted | Score: 4 | 显示更多 |
Testcase #25 | 126.657 ms | 24 MB + 536 KB | Accepted | Score: 4 | 显示更多 |