2013之前TG质量还是挺高的w
题目解释不清楚w你是懒吧啊喂！ CodeVS传送门
考虑到每个军队一定是往根的方向走（能控制更多的城市），那么只需计算往上走的方式。
这么屌的题目一看就是二分答案（虽然我不知道怎么看出来的=w=）
转为判定性问题：时间为w，能否守住所有路。
LCA计算所有军队都往上走到的最远处（或是根），记录驻扎处（或是到根的军队以后剩下的可移动长度，按剩余长度排序*）。
dfs处理没能守住的、与顶点直接相邻的边，并按边长排序。
这时在根的军队有两个决策①挑一个边过去守②（无代价）退回上来的边。
这时*处排序就有用了：对于可移动长度最短的边，一定让它退回原边（因为它是最没用的），除非原边已守。将不能退的军队从小到大和剩余的没有守住的边用恰当方式守住（仿归并O(n)），发现守不住即可退出。
上面三行有一坨剪枝（如可移动军队与未守边的数量关系等），能AC就不赘述了。
近4K毒瘤丑Code：（三个DFS我也不知道我在想啥）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define maxn 50010
#define maxm 100010
using namespace std;
struct Edge
{
int from,to,w;
};
Edge es[maxm];
int first[maxn],next[maxm],n,m,a[maxn],b[maxn],Si=0,haha=0;
int v[maxn],vv[maxn];
void AddEdge(int from,int to,int w)
{
Si++;
es[Si]=(Edge){from,to,w};
next[Si]=first[from];
first[from]=Si;
}
int p[maxn][50];//以i跳2^j格的点
long long w[maxn][50];//跳的范围内
int S[maxn];
long long l=0,r=0,u;
int h[maxn];//每点深度= =
long long t1[maxn];
int dfs(int u)
{
for (int i=first[u];i!=-1;i=next[i])
if (!h[es[i].to])
{
Edge e=es[i];
h[e.to]=h[u]+1;
p[e.to][0]=u;
w[e.to][0]=e.w;
dfs(e.to);
}
}
void init()
{
for (int j=1;(1<<j)<=n;j++)
for (int i=1;i<=n;i++)
if (p[i][j-1]!=-1)
{
p[i][j]=p[p[i][j-1]][j-1];
w[i][j]=w[i][j-1]+w[p[i][j-1]][j-1];
}
}
long long LCA(int a,int b)
{
int i,ans=0;
if (h[a]<h[b]) swap(a,b);
for (i=0;(1<<i)<=h[a];i++);
i--;
for (int j=i;j>=0;j--)
if (h[a]-(1<<j)>=h[b])
{
ans+=w[a][j];
a=p[a][j];
}
if (a==b) return ans;
for (int j=i;j>=0;j--)
{
if (p[a][j]!=-1&&p[a][j]!=p[b][j])
{
ans+=w[a][j];
a=p[a][j];
ans+=w[b][j];
b=p[b][j];
}
}
return ans+w[a][0]+w[b][0];
}
int Swim(int a,long long ww)
{
int i;
for (i=0;(1<<i)<=h[a];i++);
i--;
for (int j=i;j>=0;j--)
{
if (ww-w[a][j]>=0)
{
ww-=w[a][j];
a=p[a][j];
}
}
return a;
}
int Dfs(int u,int f)
{
S[u]=f;
for (int i=first[u];i!=-1;i=next[i])
if (!S[es[i].to])
Dfs(es[i].to,f);
}
void read()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
first[i]=-1;
for (int i=1;i<=n-1;i++)
{
long long u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
r+=w;
AddEdge(u,v,w);
AddEdge(v,u,w);
}
scanf("%d",&m);
for (int i=1;i<=m;i++)
scanf("%d",&a[i]);
h[1]=1;
dfs(1);
init();
S[1]=-1;
for (int i=first[1];i!=-1;haha++,i=next[i])
{
Dfs(es[i].to,es[i].to);
}
}
int DFS(int u)
{
if (b[u]) return 1;
v[u]=1;
int w=1,x=0;
for (int i=first[u];i!=-1;i=next[i])
if (!v[es[i].to])
{
w&=DFS(es[i].to);
if (!w) return 0;
x=1;
}
if (x==0) return 0;
return w;
}
int left1[maxn],left2[maxn];
int cmp1(int a,int b)
{
return t1[a]>t1[b];
}
int cmp2(int a,int b)
{
return es[a].w<es[b].w;
}
int check(long long w)
{
memset(b,0,sizeof(b));
memset(v,0,sizeof(v));
memset(vv,0,sizeof(vv));
int Siz1=0,Siz2=0;
for (int i=1;i<=m;i++)
{
if (t1[a[i]]>w) b[Swim(a[i],w)]=1;
else left1[++Siz1]=a[i];//w-t1[i]
}
v[1]=1;
for (int i=first[1];i!=-1;i=next[i])
if (!DFS(es[i].to)) left2[++Siz2]=i;//es[i].w
else vv[es[i].to]=1;
if (Siz1<Siz2) return 0;
sort(left1+1,left1+1+Siz1,cmp1);
sort(left2+1,left2+1+Siz2,cmp2);
int j=1;
for (int i=1;i<=Siz1;i++)
{
if (!vv[S[left1[i]]]) vv[S[left1[i]]]=1;
else
{
while (j<=Siz2&&vv[es[left2[j]].to]) j++;
while (i<=Siz1&&w-t1[left1[i]]<es[left2[j]].w) i++;
if (j>Siz2) return 1;
if (i>Siz1) return 0;
vv[es[left2[j]].to]=1;
}
}
while (j<=Siz2&&vv[es[left2[j]].to]) j++;
if (j<=Siz2) return 0;
return 1;
}
int main()
{
freopen("BL.in","r",stdin);
read();
if (haha>m)
{
printf("-1");
return 0;
}
l=0;
for (int i=1;i<=m;i++)
t1[a[i]]=LCA(a[i],1);
while (l<r)
{
u=l+r>>1;
if (check(u)) r=u;
else l=u+1;
}
long long ans;
if (r==u) ans=u;
if (l==u+1) ans=u+1;
printf("%lld",ans);
return 0;
}
评论 (0)
