#pragma GCC optimize(3)
#include<bits/stdc++.h>
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);
tree[u]=tree[ch[u][0]]*Node[u]*tree[ch[u][1]];
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 tree[u]=tree[ch[u][0]]*Node[u]*tree[ch[u][1]];//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;
tree[u]=tree[ch[u][0]]*Node[u]*tree[ch[u][1]];//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;
}
*/
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig=false, c=read(); !isdigit(c); c=read()) {
if (c == '-') iosig=true;
if (c == -1) return;
}
for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
if (iosig) x=-x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh=obuf;
inline void print(char c) {
if (ooh==obuf+OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh=obuf;
*ooh++=c;
}
template<class T>
inline void print(T x) {
static int buf[30], cnt;
if (x==0) print('0');
else {
if (x<0) print('-'), x=-x;
for (cnt=0; x; x/=10) buf[++cnt]=x%10+48;
while(cnt) print((char)buf[cnt--]);
}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }
int main(){
freopen("defense.in","r",stdin);
freopen("defense.out","w",stdout);
read(n); read(m); scanf("%s",s);
ll *P=p;
for (register int i=1; i<=n; i++) read(*(P+i));
for (register int i=1; i<n; i++){
read(u); read(v);
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--){
read(a); read(x); read(b); read(y);
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);
print(Min(tree[root].a[0][1],tree[root].a[1][1]));
g[a][x]=last1; update(a);
g[b][y]=last2; update(b);
}
flush();
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 | 46.44 us | 156 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #2 | 52.16 us | 156 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #3 | 50.67 us | 116 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #4 | 44.41 us | 116 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #5 | 54.03 us | 172 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #6 | 51.3 us | 172 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #7 | 61.04 us | 148 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #8 | 196.03 us | 296 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #9 | 194.68 us | 296 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #10 | 426.21 us | 628 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #11 | 425.97 us | 628 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #12 | 67.126 ms | 575 MB + 96 KB | Runtime Error | Score: 0 | 显示更多 |
Testcase #13 | 67.693 ms | 575 MB + 96 KB | Runtime Error | Score: 0 | 显示更多 |
Testcase #14 | 55.62 ms | 26 MB + 792 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #15 | 67.798 ms | 575 MB + 96 KB | Runtime Error | Score: 0 | 显示更多 |
Testcase #16 | 67.774 ms | 575 MB + 96 KB | Runtime Error | Score: 0 | 显示更多 |
Testcase #17 | 67.842 ms | 575 MB + 96 KB | Runtime Error | Score: 0 | 显示更多 |
Testcase #18 | 26.559 ms | 17 MB + 808 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #19 | 2 s | 8 MB + 4 KB | Time Limit Exceeded | Score: 0 | 显示更多 |
Testcase #20 | 2 s | 12 MB + 152 KB | Time Limit Exceeded | Score: 0 | 显示更多 |
Testcase #21 | 67.55 ms | 25 MB + 440 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #22 | 20.979 ms | 23 MB + 496 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #23 | 20.995 ms | 23 MB + 484 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #24 | 18.395 ms | 21 MB + 676 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #25 | 2 s | 555 MB + 1008 KB | Time Limit Exceeded | Score: 0 | 显示更多 |