简答题 偏难
#23318

保卫王国 【问题描述】 Z 国有n座城市,n − 1条双向道路,每条双向道路连接两座城市,且任意两座城市都能通过若干条道路相互到达。 Z 国的国防部长小 Z 要…

保卫王国

【问题描述】

Z 国有n座城市,n − 1条双向道路,每条双向道路连接两座城市,且任意两座城市都能通过若干条道路相互到达。

Z 国的国防部长小 Z 要在城市中驻扎军队。驻扎军队需要满足如下几个条件:

一座城市可以驻扎一支军队,也可以不驻扎军队。

由道路直接连接的两座城市中至少要有一座城市驻扎军队。

在城市里驻扎军队会产生花费,在编号为i的城市中驻扎军队的花费是pi。

小 Z 很快就规划出了一种驻扎军队的方案,使总花费最小。但是国王又给小 Z 提出了m个要求,每个要求规定了其中两座城市是否驻扎军队。小 Z 需要针对每个要求逐一给出回答。具体而言,如果国王提出的第j个要求能够满足上述驻扎条件(不需要考虑第 j 个要求之外的其它要求),则需要给出在此要求前提下驻扎军队的最小开销。如果国王提出的第j个要求无法满足,则需要输出-1 (1 ≤ j ≤ m)。现在请你来帮助小 Z。

【输入格式】

输入文件名为 defense.in。

第 1 行包含两个正整数n, m和一个字符串type,分别表示城市数、要求数和数据类型。type是一个由大写字母 A,B 或 C 和一个数字 1,2,3 组成的字符串。它可以帮助你获得部分分。你可能不需要用到这个参数。这个参数的含义在【数据规模与约定】中有具体的描述。

第2行n个整数pi,表示编号i的城市中驻扎军队的花费。

接下来n − 1行,每行两个正整数u, v,表示有一条u到v的双向道路。

接下来m行,第j行四个整数a, x, b, y(a ≠ b),表示第j个要求是在城市a驻扎x支军队,在城市b驻扎y支军队。其中,x 、 y 的取值只有 0 或 1:若 x 为 0,表示城市 a 不得驻扎军队,若 x 为 1,表示城市 a 必须驻扎军队;若 y 为 0,表示城市 b 不得驻扎军队,若 y 为 1,表示城市 b 必须驻扎军队。

输入文件中每一行相邻的两个数据之间均用一个空格分隔。

【输出格式】

输出文件名为 defense.out。

输出共m行,每行包含 1 个整数,第j行表示在满足国王第j个要求时的最小开销,如果无法满足国王的第j个要求,则该行输出-1。

【输入输出样例 1】

【样例解释】

对于第一个要求,在 4 号和 5 号城市驻扎军队时开销最小。

对于第二个要求,在 1 号、2 号、3 号城市驻扎军队时开销最小。

第三个要求是无法满足的,因为在 1 号、5 号城市都不驻扎军队就意味着由道路直接连

接的两座城市中都没有驻扎军队。

【数据规模与约定】

对于 100%的数据,n, m ≤ 300000,1 ≤ pi ≤ 100000。

数据类型的含义:

A:城市i与城市i + 1直接相连。

B:任意城市与城市 1 的距离不超过 100(距离定义为最短路径上边的数量),即如果这棵树以 1 号城市为根,深度不超过 100。

C:在树的形态上无特殊约束。

1:询问时保证a = 1, x = 1,即要求在城市 1 驻军。对b, y没有限制。

2:询问时保证a, b是相邻的(由一条道路直接连通)

3:在询问上无特殊约束。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<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&lt;stdio.h&gt;</p><p style="text-align: left;">#include&lt;string.h&gt;</p><p style="text-align: left;">#include&lt;algorithm&gt;</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&lt;=b;++i)</p><p style="text-align: left;">#define fd(i,a,b) for (reg i=a;i&gt;=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&lt;'0' || '9'&lt;ch){if (ch=='-')f=-1;ch=getchar();}</p><p style="text-align: left;"><span style="white-space:pre"> </span>while ('0'&lt;=ch &amp;&amp; ch&lt;='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&lt;y?x:y;</p><p style="text-align: left;">}</p><p style="text-align: left;">O3 inline void swap(ll &amp;x,ll &amp;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",&amp;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 &amp;&amp; ((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]&lt;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]]&gt;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>
这道题暂未补解析。