代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=401000;
const long long INF=1e14;
int n,m;
long long val[MAXN];
int siz[MAXN],son[MAXN],fa[MAXN],lsiz[MAXN],ch[MAXN][2];
int vis[MAXN],st[MAXN];
int tot,front[MAXN],to[MAXN],nxt[MAXN];
char s[5];
struct matrix{
    long long a[2][2];
    void clear()
    {
        a[0][0]=a[0][1]=a[1][0]=a[1][1]=-INF;
    }
    matrix operator *(const matrix&b)const
    {
        matrix c;
        c.clear();
        for(int i=0;i<=1;i++)
            for(int j=0;j<=1;j++)
                for(int k=0;k<=1;k++)
                    c.a[i][j]=max(a[i][k]+b.a[k][j],c.a[i][j]);
        return c;
    }
}num[MAXN],sum[MAXN];
void init(int u,int v)
{
    to[++tot]=v;
    nxt[tot]=front[u];
    front[u]=tot;
}
void dfs(int u,int father)
{
    siz[u]=1;
    for(int i=front[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v!=father)
        {
            dfs(v,u);
            siz[u]+=siz[v];
            if(siz[v]>siz[son[u]])
                son[u]=v;
        }
    }
}
void trans(int u,int v)
{
    num[u].a[0][0]+=max(sum[v].a[0][0],sum[v].a[1][0]);
    num[u].a[0][1]=num[u].a[0][0];
    num[u].a[1][0]+=sum[v].a[0][0];
}
void updata(int u)
{
    sum[u]=sum[ch[u][0]]*num[u]*sum[ch[u][1]];
}
int sbuild(int l,int r)
{
    if(l>r)return 0;
    int sum=0;
    for(int i=l;i<=r;i++)		sum+=lsiz[st[i]];
    for(int i=l,tmp=lsiz[st[i]];i<=r;i++,tmp+=lsiz[st[i]])
        if(tmp*2>=sum)
        {
            int ls=sbuild(l,i-1),rs=sbuild(i+1,r);
            ch[st[i]][0]=ls,ch[st[i]][1]=rs;
            if(ls)fa[ls]=st[i];
            if(rs)fa[rs]=st[i];
            updata(st[i]);
            return st[i];
        }
}
int build(int u)
{
    for(int i=u;i;i=son[i])vis[i]=1;
    for(int i=u;i;i=son[i])
        for(int j=front[i];j;j=nxt[j])
        {
            int v=to[j];
            if(!vis[v])
            {
                int tmp=build(v);
                trans(i,tmp);
                fa[tmp]=i;
            }
        }
    int tp=0;
    for(int i=u;i;i=son[i])st[++tp]=i;
    for(int i=u;i;i=son[i])lsiz[i]=siz[i]-siz[son[i]];
    return sbuild(1,tp);
}
void change(int u,long long d)
{
    num[u].a[1][0]+=d-val[u];
    val[u]=d;
    for(;u;u=fa[u])
        if(fa[u]&&ch[fa[u]][0]!=u&&ch[fa[u]][1]!=u)
        {
            num[fa[u]].a[0][0]-=max(sum[u].a[0][0],sum[u].a[1][0]);
            num[fa[u]].a[0][1]=num[fa[u]].a[0][0];
            num[fa[u]].a[1][0]-=sum[u].a[0][0];
            updata(u);
            num[fa[u]].a[0][0]+=max(sum[u].a[0][0],sum[u].a[1][0]);
            num[fa[u]].a[0][1]=num[fa[u]].a[0][0];
            num[fa[u]].a[1][0]+=sum[u].a[0][0];
        }
        else
            updata(u);
}
int main()
{
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
    long long ans=0;
    scanf("%d%d",&n,&m);
    scanf("%s",s);
    for(int i=1;i<=n;i++)scanf("%lld",&val[i]),ans+=val[i];
    for(int i=1,u,v;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        init(u,v);
        init(v,u);
    }
    for(int i=1;i<=n;i++)num[i].a[1][0]=val[i];
    for(int i=1;i<=n;i++)sum[i]=num[i];
    sum[0].a[0][0]=sum[0].a[1][1]=0;
    sum[0].a[1][0]=sum[0].a[0][1]=-INF;
    dfs(1,0);	
    int root=build(1);
    for(int i=1,a,x,b,y,ox,oy;i<=m;i++)
    {
        scanf("%d%d%d%d",&a,&x,&b,&y);
        if(x==y&&y==0)
        {
            int flag=0;
            for(int j=front[a];j;j=nxt[j])
                if(to[j]==b)
                {
                    flag=1;
                    break;
                }
            if(flag)
            {
                printf("-1\n");
                continue;
            }
        }
        ox=val[a],oy=val[b];
        long long tmp=ans;
        if(x)
            change(a,-INF);
        else
            change(a,INF),tmp+=INF-ox;
        if(y)
            change(b,-INF);
        else
            change(b,INF),tmp+=INF-oy;
        printf("%lld\n",tmp-max(sum[root].a[0][0],sum[root].a[1][0]));
        change(a,ox);
        change(b,oy);
    }
    return 0;
}

评测结果