答案与解析
正确答案:<p style="text-align: left;">#pragma GCC optimize("O3")</p><p style="text-align: left;">#pragma G++ optimize("O3")</p><p style="text-align: left;">#include<stdio.h></p><p style="text-align: left;">#include<string.h></p><p style="text-align: left;">#include<algorithm></p><p style="text-align: left;">#define MAXN 100005</p><p style="text-align: left;">#define MAXM MAXN*2</p><p style="text-align: left;">#define ll long long</p><p style="text-align: left;">#define reg register ll</p><p style="text-align: left;">#define INF 1000000000000000007ll</p><p style="text-align: left;">#define fo(i,a,b) for (reg i=a;i<=b;++i)</p><p style="text-align: left;">#define fd(i,a,b) for (reg i=a;i>=b;--i)</p><p style="text-align: left;">#define rep(i,a) for (reg i=last[a];i;i=next[i])</p><p style="text-align: left;">#define O3 __attribute__((optimize("-O3")))</p><p><br style="text-align: left;"/></p><p style="text-align: left;">ll last[MAXM],next[MAXM],tov[MAXM];</p><p style="text-align: left;">ll p[MAXN],depth[MAXN],fa[MAXN];</p><p style="text-align: left;">ll f[MAXN][2],g[MAXN][2];</p><p style="text-align: left;">ll anc[MAXN][21];</p><p style="text-align: left;">ll n,m,tot,ans;</p><p style="text-align: left;">char type[5];</p><p><br style="text-align: left;"/></p><p style="text-align: left;">struct node</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>ll a[2][2];</p><p style="text-align: left;">}dis[MAXN][21],A,B,C;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">O3 inline ll read()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>ll x=0,f=1;char ch=getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}</p><p style="text-align: left;"><span style="white-space:pre"> </span>while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>return x*f;</p><p style="text-align: left;">}</p><p style="text-align: left;">O3 inline ll min(ll x,ll y)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>return x<y?x:y;</p><p style="text-align: left;">}</p><p style="text-align: left;">O3 inline void swap(ll &x,ll &y)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>x=x+y,y=x-y,x=x-y;</p><p style="text-align: left;">}</p><p style="text-align: left;">O3 inline void link(ll x,ll y)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>next[++tot]=last[x],last[x]=tot,tov[tot]=y;</p><p style="text-align: left;">}</p><p style="text-align: left;">O3 inline void dfs1(ll x)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>depth[x]=depth[fa[x]]+1,anc[x][0]=fa[x];</p><p style="text-align: left;"><span style="white-space:pre"> </span>fo(i,1,20)anc[x][i]=anc[anc[x][i-1]][i-1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>f[x][0]=0,f[x][1]=p[x];</p><p style="text-align: left;"><span style="white-space:pre"> </span>rep(i,x)if (tov[i]!=fa[x])</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>fa[tov[i]]=x,dfs1(tov[i]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>f[x][0]+=f[tov[i]][1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>f[x][1]+=min(f[tov[i]][0],f[tov[i]][1]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p style="text-align: left;">O3 inline void dfs2(ll x)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (x==1)g[x][0]=f[x][0],g[x][1]=f[x][1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>else</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>g[x][0]=f[x][0]+g[fa[x]][1]-min(f[x][0],f[x][1]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>g[x][1]=f[x][1]+min(g[fa[x]][0]-f[x][1],g[fa[x]][1]-min(f[x][0],f[x][1]));</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>rep(i,x)if (tov[i]!=fa[x])</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>dis[tov[i]][0].a[0][0]=INF;</p><p style="text-align: left;"><span style="white-space:pre"> </span>dis[tov[i]][0].a[1][0]=f[x][0]-f[tov[i]][1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>dis[tov[i]][0].a[0][1]=f[x][1]-min(f[tov[i]][0],f[tov[i]][1]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>dis[tov[i]][0].a[1][1]=f[x][1]-min(f[tov[i]][0],f[tov[i]][1]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>dfs2(tov[i]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p style="text-align: left;">O3 inline node merge(node A,node B)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>memset(C.a,60,sizeof(C.a));</p><p style="text-align: left;"><span style="white-space:pre"> </span>fo(i,0,1)fo(j,0,1)fo(k,0,1)</p><p style="text-align: left;"><span style="white-space:pre"> </span>C.a[i][j]=min(C.a[i][j],A.a[i][k]+B.a[k][j]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>return C;</p><p style="text-align: left;">}</p><p style="text-align: left;">O3 int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>freopen("defense.in","r",stdin);</p><p style="text-align: left;"><span style="white-space:pre"> </span>freopen("defense.out","w",stdout);</p><p style="text-align: left;"><span style="white-space:pre"> </span>//freopen("readin.txt","r",stdin);</p><p style="text-align: left;"><span style="white-space:pre"> </span>n=read(),m=read(),scanf("%s",&type);</p><p style="text-align: left;"><span style="white-space:pre"> </span>fo(i,1,n)p[i]=read();</p><p style="text-align: left;"><span style="white-space:pre"> </span>fo(i,1,n-1)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>ll x=read(),y=read();</p><p style="text-align: left;"><span style="white-space:pre"> </span>link(x,y),link(y,x);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>dfs1(1),dfs2(1);</p><p style="text-align: left;"><span style="white-space:pre"> </span>fo(j,1,20)fo(i,1,n)dis[i][j]=merge(dis[i][j-1],dis[anc[i][j-1]][j-1]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>while (m--)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>ll a=read(),x=read(),b=read(),y=read();</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (x+y==0 && ((fa[a]==b) || (fa[b]==a)))</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>printf("-1\n");</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (depth[a]<depth[b])swap(a,b),swap(x,y);</p><p style="text-align: left;"><span style="white-space:pre"> </span>memset(A.a,60,sizeof(A.a));</p><p style="text-align: left;"><span style="white-space:pre"> </span>memset(B.a,60,sizeof(B.a));</p><p style="text-align: left;"><span style="white-space:pre"> </span>A.a[x][x]=f[a][x],B.a[y][y]=f[b][y];</p><p style="text-align: left;"><span style="white-space:pre"> </span>fd(i,20,0)if (depth[anc[a][i]]>depth[b])</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>A=merge(A,dis[a][i]),a=anc[a][i];</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (fa[a]==b)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>printf("%lld\n",y==0?g[b][0]-f[a][1]+A.a[x][1]:</p><p style="text-align: left;"><span style="white-space:pre"> </span>g[b][1]-min(f[a][0],f[a][1])+min(A.a[x][0],A.a[x][1]));</p><p style="text-align: left;"><span style="white-space:pre"> </span>continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>if (depth[a]!=depth[b])A=merge(A,dis[a][0]),a=fa[a];</p><p style="text-align: left;"><span style="white-space:pre"> </span>fd(i,20,0)if (anc[a][i]!=anc[b][i])</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>A=merge(A,dis[a][i]),B=merge(B,dis[b][i]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>a=anc[a][i],b=anc[b][i];</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>printf("%lld\n",min(g[fa[a]][0]-f[a][1]-f[b][1]+A.a[x][1]+B.a[y][1],</p><p style="text-align: left;"><span style="white-space:pre"> </span>g[fa[a]][1]-min(f[a][0],f[a][1])-min(f[b][0],f[b][1])+min(A.a[x][0],A.a[x][1])+min(B.a[y][0],B.a[y][1])));</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。