[CF526G]Spiders Evil Plan

题目大意：
　　给出一个$n(n\leq 10^5)$个结点的带边权的树，$q(q\leq 10^5)$个询问，每次询问用$y$条路径覆盖整棵树且覆盖$x$至少一次，最多能覆盖的道路长度是多少？
　　强制在线。

思路：
　　考虑固定$x$时的情况，我们可以使用长链剖分，然后贪心地选择$2y$条长链，每$2$条可以组成一条路径，这样就找出了$y$条路径的最优方案，均摊复杂度$O(n)$。
　　现在考虑$x$不固定的情况，对于每个询问分别做一次长链剖分，复杂度是$O(nq)$的，显然会超时。
　　考虑如何只用一次树剖解决所有的询问。
　　问题也就变成了如何确定一个根，使得所有询问的覆盖方案中，每条路径都会经过这个根。
　　显然，经过一点最长的路径肯定会经过直径的一个端点。
　　因此我们可以将直径的任一端点作为根结点开始树剖，然后贪心地选$2y-1$条最长链（最长的一条本身就是一条路径），这样时间复杂度就是$O(n+q)$。
　　但是这样并不是完全正确的，因为$2y-1$条最长链不一定能涵盖$x$。
　　因此我们需要将其中一条替换成一条经过$x$的链。
　　具体分为以下三种情况：
　　　　1.直接把最短的一整条链去掉；
　　　　2.把从根结点出发的一条链去掉上面一半；
　　　　3.把离$x$最近的一条链去掉下面$y$一半。

 #include<queue>

 #include<cstdio>

 #include<cctype>

 #include<vector>

 #include<algorithm>

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int N=;

 struct Edge {

     int to,w;

 };

 bool vis[N];

 std::queue<int> q;

 std::vector<Edge> e[N];

 int dis[N],far[N],par[N],top[N],son[N],leaf[N],rank[N],sum[N],root;

 inline void add_edge(const int &u,const int &v,const int &w) {

     e[u].push_back((Edge){v,w});

     e[v].push_back((Edge){u,w});

 }

 inline void bfs() {

     q.push(root=);

     vis[]=true;

     while(!q.empty()) {

         const int x=q.front();

         q.pop();

         if(dis[x]>dis[root]) root=x;

         for(register unsigned i=;i<e[x].size();i++) {

             const int &y=e[x][i].to,&w=e[x][i].w;

             if(vis[y]) continue;

             dis[y]=dis[x]+w;

             vis[y]=true;

             q.push(y);

         }

     }

     dis[root]=;

 }

 void dfs1(const int &x,const int &par) {

     son[x]=;

     ::par[x]=par;

     far[x]=dis[x];

     for(unsigned i=;i<e[x].size();i++) {

         const int &y=e[x][i].to,&w=e[x][i].w;

         if(y==par) continue;

         dis[y]=dis[x]+w;

         dfs1(y,x);

         if(far[y]>far[x]) {

             far[x]=far[y];

             son[x]=y;

         }

     }

 }

 void dfs2(const int &x) {

     if(x==son[par[x]]) {

         top[x]=top[par[x]];

     } else {

         top[x]=x;

     }

     if(son[x]) {

         dfs2(son[x]);

     } else {

         leaf[++leaf[]]=x;

     }

     for(unsigned i=;i<e[x].size();i++) {

         const int &y=e[x][i].to;

         if(y==par[x]||y==son[x]) continue;

         dfs2(y);

     }

 }

 inline bool cmp(const int &x,const int &y) {

     return dis[x]-dis[par[top[x]]]>dis[y]-dis[par[top[y]]];

 }

 inline int query(const int &x,const int &y) {

     if(rank[top[x]]<=y*-) {

         return sum[std::min(y*-,leaf[])];

     }

     int u=x;

     while(rank[top[u]]>y*-) {

         u=par[top[u]];

     }

     return sum[y*-]-std::min(std::min(sum[y*-]-sum[y*-],far[u]-dis[u]),dis[u])+(far[x]-dis[u]);

 }

 int main() {

     const int n=getint(),q=getint();

     for(register int i=;i<n;i++) {

         const int u=getint(),v=getint(),w=getint();

         add_edge(u,v,w);

     }

     bfs();

     dfs1(root,);

     dfs2(root);

     std::sort(&leaf[],&leaf[+leaf[]],cmp);

     for(register int i=;i<=leaf[];i++) {

         rank[top[leaf[i]]]=i;

         sum[i]=sum[i-]+dis[leaf[i]]-dis[par[top[leaf[i]]]];

     }

     for(register int i=,ans=;i<q;i++) {

         const int x=(getint()+ans-)%n+,y=(getint()+ans-)%n+;

         printf("%d\n",ans=query(x,y));

     }

     return ;

 }

巴特西

[CF526G]Spiders Evil Plan

最新文章

热门文章