【题解】洛谷P2680[NOIP2015]运输计划 树链剖分+树上差分+LCA+二分
学习了大佬题解,主要思路摘抄如下:
先LCA一遍,记下每个任务的起点,终点,公共祖先,所需时间
然后二分答案,统计不满足答案的任务tot,然后维护一个sum[i],
对于每个不满足条件的任务,sum[起点]++,sum[终点]++,sum[公共祖先]-=2,
并将它们的sum值传到父亲结点,最后看是否能找出某个点i,使sum[i]=tot并且
连到这个点的边权值>= 最大任务时间-答案,如果能,这个答案即为可行答案。
感觉就是标记每个点经过多少不满足条件的边,然后看这个点连向父节点的边权改为0后能不能满足条件
自己在模拟的时候打的是暴力
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
template<typename tp>inline void read(tp &x)
{
int f=0;char ch=getchar();x=0;
while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
const int N=3e5+10;
int n,m,tot=1,hd[N],maxn,dis[N],dep[N],fa[N],ans=0x7fffffff,sz[N],top[N],son[N],edge[N],INF,sum[N];
struct Edge{
int v,nx,w;
}e[N<<1];
struct node{
int u,v;
}ask[N];
struct Node{
int u,v,anc,dis;
}lca[N];
inline void add(int u,int v,int w)
{
e[++tot].v=v;
e[tot].w=w;
e[tot].nx=hd[u];
hd[u]=tot;
}
namespace pts20{
void dfs(int u,int f)
{
fa[u]=f;
for(int i=hd[u];i;i=e[i].nx)
{
int v=e[i].v;if(v==f)continue;
dis[v]=dis[u]+e[i].w;
dfs(v,u);
}
}
void dfs2(int u,int son)
{
for(int i=hd[u];i;i=e[i].nx)
{
int v=e[i].v;
if(v==son)continue;
if(v==fa[u]){maxn=max(maxn,e[i].w),dfs2(v,u);break;}
}
}
inline void solve()
{
int st,ed;read(st);read(ed);
dfs(st,0);dfs2(ed,ed);printf("%d\n",dis[ed]-maxn);
}
}
namespace pts30{//在学校OJ能得30分
inline void dij(int st,int ed)
{
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;while(!q.empty())q.pop();q.push(make_pair(0,st));
memset(dis,0x3f,sizeof(dis));dis[st]=0;static int vis[N];memset(vis,0,sizeof(vis));
while(!q.empty())
{
int u=q.top().second;q.pop();vis[u]=0;
for(int i=hd[u];i;i=e[i].nx)
{
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w)
{
dis[v]=dis[u]+e[i].w;
if(!vis[v])vis[v]=1,q.push(make_pair(dis[v],v));
}
}
}
maxn=max(maxn,dis[ed]);
}
inline void solve()
{
for(int i=1;i<=m;i++)
read(ask[i].u),read(ask[i].v);
for(int i=2;i<=tot;i+=2)
{
int tmp=e[i].w;e[i].w=e[i^1].w=0;
maxn=0;
for(int j=1;j<=m;j++)
dij(ask[j].u,ask[j].v);
ans=min(ans,maxn);
e[i].w=e[i^1].w=tmp;
}
printf("%d\n",ans);
}
}
namespace ac{
void dfs1(int u,int f)
{
dep[u]=dep[f]+1;fa[u]=f;sz[u]=1;
int maxson=-1;
for(int i=hd[u];i;i=e[i].nx)
{
int v=e[i].v;
if(v==f)continue;
edge[v]=i;dis[v]=dis[u]+e[i].w;
dfs1(v,u);sz[u]+=sz[v];
if(sz[v]>maxson)son[u]=v,maxson=sz[v];
}
}
void dfs2(int u,int topf)
{
top[u]=topf;
if(son[u])dfs2(son[u],topf);
for(int i=hd[u];i;i=e[i].nx)
{
int v=e[i].v;
if(v==son[u]||v==fa[u])continue;
dfs2(v,v);
}
}
inline int LCA(int x,int y)//树剖求LCA
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);//x顶端深度更深
x=fa[top[x]];//x跳到x所在链顶端上面一个点
}
if(dep[x]>dep[y])swap(x,y);
return x;
}
void dfs3(int u,int f)//求子树中差分数组和
{
for(int i=hd[u];i;i=e[i].nx)
{
int v=e[i].v;
if(v==f)continue;
dfs3(v,u);sum[u]+=sum[v];
}
}
inline bool check(int lim)
{
memset(sum,0,sizeof(sum));
int p=0,cnt=0;
for(int i=1;i<=m;i++)
if(lca[i].dis>lim)
{
cnt++;
sum[lca[i].u]++;
sum[lca[i].v]++;
sum[lca[i].anc]-=2;
p=max(p,lca[i].dis-lim);
}
dfs3(1,1);
for(int i=1;i<=n;i++)
if(sum[i]==cnt&&e[edge[i]].w>=p)return 1;
return 0;
}
inline void solve()
{
dfs1(1,0);dfs2(1,1);
for(int i=1;i<=m;i++)
{
read(lca[i].u);read(lca[i].v);
lca[i].anc=LCA(lca[i].u,lca[i].v);
lca[i].dis=dis[lca[i].u]+dis[lca[i].v]-2*dis[lca[i].anc];
INF=max(INF,lca[i].dis);
}
int l=0,r=INF,ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d\n",ans);
}
}
int main()
{
//freopen("in.txt","r",stdin);
read(n);read(m);
for(int i=1,u,v,w;i<n;i++)
read(u),read(v),read(w),add(u,v,w),add(v,u,w);
//if(m==1)pts20::solve();
//else pts30::solve();
ac::solve();
return 0;
}
总结
综合性很大的题。树剖求LCA的操作还没见过。