酪奶

树上差分 二分

---

题面

给一棵$n$个点、$n$条边的基环树，钦定要走环就必须要经过某条边，因此两点间路径唯一。边有边权，现有$m$次行动，每次将两点间路径上的边权同时减去一值，问第几次行动后出现负边权。

• $20pts\ n\leq10^3,m\leq10^4$
• $40pts\ m\leq10^5$
• $ex20pts\ the\ graph\ is\ only\ a\ single\ circle$
• $80pts\ m\leq10^6$
• $100pts\ n\leq10^5,m\leq10^7$

吐槽

毒瘤出题人$hjt$坑害机房多位大佬，出现多人怒码$3h$却$boom\ 0$的惨状。
好像我也只有10分

解析

$20pts$算法

把图看成根节点连成一个环的几颗树的集合。
暴力模拟即可。
复杂度$O(nm)$
然而打不对。。。

$ex20pts$算法

可以用一颗线段树维护整个环的边权。

$80pts$算法

线段树维护环，树剖+线段树维护几颗树。
即数据结构优化后的模拟
复杂度降到$O(mlog^2n)$
据说码量可以达到$6KB$？？？

还有一种方法。
去掉钦定边，图就变成了一棵树。把该边一个点作为树的根$rt$，另一点为$re$。
如果两点路径不经过环，直接修改即可。
如果经过，修改一个点到$rt$路径，另一点到$re$的路径和那条钦定边。
判断方法是两点与$re$在树上的$lca$（分别代表着两点进入环时到的点）不同，如果$lca$深度小就连$rt$，大就连$re$。
复杂度同，但常数肯定小一些，因不需要线段树。

$ST$表求$LCA$

原理：在$DFS$序中，两个点的$LCA$出现在两个点第一次出现的位置之间，且为中间这些数中深度最小的点。
显然。

il void dfs(re int u,re int deep)
{
  id[u]=++top;sta[top]=u;d[top]=deep;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(id[v]) continue;
      dfs(v,deep+1);
      sta[++top]=u;d[top]=deep;
    }
}
int main()
{
  memset(h,-1,sizeof(h));
  n=gi();q=gi();rt=gi();
  fp(i,1,n-1)
    {
      re int u=gi(),v=gi();
      add(u,v);add(v,u);
    }
  dfs(rt,1);
  fp(i,1,top) f[0][i]=d[i],dp[0][i]=sta[i];
  for(re int i=1;i<=log(top)/log(2);i++)
    for(re int j=1;j<=top-(1<<i)+1;j++)
      {
    if(f[i-1][j]<f[i-1][j+(1<<(i-1))]) f[i][j]=f[i-1][j],dp[i][j]=dp[i-1][j];
    else f[i][j]=f[i-1][j+(1<<(i-1))],dp[i][j]=dp[i-1][j+(1<<(i-1))];
      }
  //printf("good\n");
  fp(i,1,q)
  {
      re int l=gi(),r=gi();
      l=id[l],r=id[r];
      if(l>r) swap(l,r);
      re int k=0;
      while((1<<k)<=r-l+1) ++k;
      --k;
      if(f[k][l]<f[k][r-(1<<k)+1]) printf("%d\n",dp[k][l]);
      else printf("%d\n",dp[k][r-(1<<k)+1]);
  }
  return 0;
}

$100pts$算法

此题原型$NOIP2012$借教室。
毒瘤改了一下变成在基环树边上建教室。。。。

于是我们可以发现，我们可以用树上差分来维护树上边权。
给两点之间的路径权值$-w$的具体做法,就变成了在两个点上都打上$-w$的标记,再在$lca$上打$+2w$的标记。
当然，打上所有标记后我们是不能得到某一步后（过程中）的边权的。
所以我们要用二分答案来逼近出现负边权的确切次数。

然而，求$lca$和求$1-mid$次操作后的边权都是复杂度瓶颈，复杂度可达$O(mlogmlogn)$。
注意到二分时每次重求边权未免过于浪费，可以在上一次的基础上继续打标记（往前推就打反标记)，再继续推。复杂度可降为$O(mlogn)$。

$$O(\frac{m}{2}+\frac{m}{4}+\frac{m}{8}+...)=O(m)$$
在此题中，求任意两点间的$lca$，在线算法树剖和倍增复杂度都会达到$O(mlogn)$，$ST$表求$lca$预处理复杂度$O(nlogn)$,在线$O(m)$。
总复杂度$O(nlogn+m)$。

作为一只懒于打数据结构的蒟蒻，我当然选择方法二啦
树链剖分求$LCA$，期望得分$80pts$

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define ls x<<1
#define rs x<<1|1
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e5+100;
unsigned int SA,SB,SC;
int n,m,h[N],cnt,hu,hv,hw,rt,d[N],f[N],sz[N],son[N],top[N],L[N],R[N],id[N],tim,las,c[N],flag=0;
bool vis[N<<1];
struct dat{int u,v,w,tag,lca,gen,lca1;}a[N*100];
struct Edge{int to,nxt,w,id;}e[N<<1];
il void add(re int u,re int v,re ll w,re int id){e[++cnt]=(Edge){v,h[u],w,id};h[u]=cnt;}
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
unsigned int rng61()
{
  SA^=SA<<16;SA^=SA>>5;SA^=SA<<1;
  unsigned int  t=SA;
  SA=SB;SB=SC;SC^=t^SA;
  return SC;
}
il void dfs1(re int u,re int fa)
{
  d[u]=d[fa]+1;f[u]=fa;sz[u]=1;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      dfs1(v,u);
      sz[u]+=sz[v];
      if(sz[son[u]]<sz[v]) son[u]=v;
    }
}
il void dfs2(re int u,re int up)
{
  top[u]=up;L[u]=++tim;id[tim]=u;
  if(son[u]) dfs2(son[u],up);
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==f[u]||v==son[u]) continue;
      dfs2(v,v);
    }
  R[u]=tim;
}
il int getlca(re int u,re int v)
{
  while(top[u]^top[v])
    {
      if(d[top[u]]<d[top[v]]) swap(u,v);
      u=f[top[u]];
    }
  return d[u]<d[v]?u:v;
}
il void dfs(re int u,re int fa)
{
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      dfs(v,u);
      c[u]+=c[v];
      e[i].w+=c[v];
      c[v]=0;
      if(e[i].w<0) flag=1,vis[e[i].id]=1;else vis[e[i].id]=0;
    }
}
il int check(re int x)
{
  flag=0;
  if(las<x)
  {
    fp(i,las+1,x)
      {
        re int u=a[i].u,v=a[i].v,w=a[i].w,lca=a[i].lca,gen=a[i].gen,lca1=a[i].lca1;
    if(a[i].tag) c[u]-=w,c[v]-=w,c[lca]+=2*w;
    else c[gen]-=w,c[rt]+=w,c[lca]-=w,c[hv]-=w,c[lca1]+=2*w,hw-=w;
      }
    dfs(rt,0);
    if(hw<0) flag=1,vis[1]=1;else vis[1]=0;
  }
  else
  {
    fq(i,las,x+1)
      {
        re int u=a[i].u,v=a[i].v,w=a[i].w,lca=a[i].lca,gen=a[i].gen,lca1=a[i].lca1;
    if(a[i].tag) c[u]+=w,c[v]+=w,c[lca]-=2*w;
    else c[gen]+=w,c[rt]-=w,c[lca]+=w,c[hv]+=w,c[lca1]-=2*w,hw+=w;
      }
    dfs(rt,0);
    if(hw<0) flag=1,vis[1]=1;else vis[1]=0;
  }
  las=x;
  return flag;
}
int main()
{
  freopen("eseehc.in","r",stdin);
  freopen("eseehc.out","w",stdout);
  memset(h,-1,sizeof(h));
  SA=gi();SB=gi();SC=gi();n=gi();m=gi();
  fp(i,1,m) a[i].u=rng61()%n+1,a[i].v=rng61()%n+1,a[i].w=rng61()%100+1;
  fp(i,1,n)
  {
    re int u=gi(),v=gi(),w=gi();
    if(i==1) rt=hu=u,hv=v,hw=w;
    else add(u,v,w,i),add(v,u,w,i);
  }
  dfs1(rt,0);dfs2(rt,rt);
  fp(i,1,m)
   {
      re int u=a[i].u,v=a[i].v;
      a[i].tag=(getlca(u,hv)==getlca(v,hv));
      if(a[i].tag) a[i].lca=getlca(u,v);
      else if(d[getlca(v,hv)]>=d[getlca(u,hv)]) a[i].gen=u,a[i].lca=v,a[i].lca1=getlca(v,hv);
      else a[i].gen=v,a[i].lca=u,a[i].lca1=getlca(u,hv);
      //printf("%d %d %d %d %d %d\n",u,v,a[i].tag,a[i].lca,getlca(u,hv),getlca(v,hv));
   }
  re int l=0,r=m+100;
  while(l<r)
    {
      re int mid=l+r>>1;
      if(check(mid)) r=mid;
      else l=mid+1;
    }
  if(r==m+100) puts("-1");
  else
    {
      check(r);
      printf("%d\n",r);
      fp(i,1,n) if(vis[i]) printf("%d ",i);
      puts("");
    }
  fclose(stdin);
  fclose(stdout);
  return 0;
}

注意到几个细节。
可能你在退出二分时，保留的状态是$ans-1$时的状态，导致找不到边权$<0$的边。
所以输出答案前要把状态推到答案那一步。

并且将差分标记上传后要清$0$！！！

没调完的$ST$表求$LCA$，期望$100pts$

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define ls x<<1
#define rs x<<1|1
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e5+100;
unsigned int SA,SB,SC;
int n,m,h[N],cnt,hu,hv,hw,rt,d[N],dd[N],sta[N<<2],top,dp[20][N<<2],f[20][N<<2],id[N],las,flag=0,c[N];
bool vis[N<<1];
struct dat{int u,v,w,tag,lca,gen,lca1;}a[N*100];
struct Edge{int to,nxt,w,id;}e[N<<1];
il void add(re int u,re int v,re ll w,re int id){e[++cnt]=(Edge){v,h[u],w,id};h[u]=cnt;}
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
unsigned int rng61()
{
  SA^=SA<<16;SA^=SA>>5;SA^=SA<<1;
  unsigned int  t=SA;
  SA=SB;SB=SC;SC^=t^SA;
  return SC;
}
il void dfs(re int u,re int fa)
{
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      dfs(v,u);
      c[u]+=c[v];
      e[i].w+=c[v];
      c[v]=0;
      if(e[i].w<0) flag=1,vis[e[i].id]=1;else vis[e[i].id]=0;
    }
}
il void dfs1(re int u,re int deep)
{
  //printf("%d %d\n",u,deep);
  id[u]=++top;sta[top]=u;d[top]=deep;dd[u]=deep;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(id[v]) continue;
      dfs1(v,deep+1);
      sta[++top]=u;d[top]=deep;
    }
}
il int getlca(re int l,re int r)
{
  l=id[l],r=id[r];
  if(l>r) swap(l,r);
  re int k=0;
  while((1<<k)<=r-l+1) ++k;
  --k;
  if(f[k][l]<f[k][r-(1<<k)+1]) return dp[k][l];
    else return dp[k][r-(1<<k)+1];
}
il int check(re int x)
{
  flag=0;
  if(las<x)
  {
    fp(i,las+1,x)
      {
        re int u=a[i].u,v=a[i].v,w=a[i].w,lca=a[i].lca,gen=a[i].gen,lca1=a[i].lca1;
    if(a[i].tag) c[u]-=w,c[v]-=w,c[lca]+=2*w;
    else c[gen]-=w,c[rt]+=w,c[lca]-=w,c[hv]-=w,c[lca1]+=2*w,hw-=w;
      }
    dfs(rt,0);
    if(hw<0) flag=1,vis[1]=1;else vis[1]=0;
  }
  else
  {
    fq(i,las,x+1)
      {
        re int u=a[i].u,v=a[i].v,w=a[i].w,lca=a[i].lca,gen=a[i].gen,lca1=a[i].lca1;
    if(a[i].tag) c[u]+=w,c[v]+=w,c[lca]-=2*w;
    else c[gen]+=w,c[rt]-=w,c[lca]+=w,c[hv]+=w,c[lca1]-=2*w,hw+=w;
      }
    dfs(rt,0);
    if(hw<0) flag=1,vis[1]=1;else vis[1]=0;
  }
  las=x;
  return flag;
}
int main()
{
  freopen("eseehc.in","r",stdin);
  freopen("eseehc.out","w",stdout);
  memset(h,-1,sizeof(h));
  SA=gi();SB=gi();SC=gi();n=gi();m=gi();
  fp(i,1,m) a[i].u=rng61()%n+1,a[i].v=rng61()%n+1,a[i].w=rng61()%100+1;
  fp(i,1,n)
  {
    re int u=gi(),v=gi(),w=gi();
    if(i==1) rt=hu=u,hv=v,hw=w;
    else add(u,v,w,i),add(v,u,w,i);
  }
  dfs1(rt,1);
  fp(i,1,top) f[0][i]=d[i],dp[0][i]=sta[i];
  for(re int i=1;i<=log(top)/log(2);i++)
    for(re int j=1;j<=top-(1<<i)+1;j++)
      if(f[i-1][j]<f[i-1][j+(1<<(i-1))]) f[i][j]=f[i-1][j],dp[i][j]=dp[i-1][j];
      else f[i][j]=f[i-1][j+(1<<(i-1))],dp[i][j]=dp[i-1][j+(1<<(i-1))];
  fp(i,1,m)
   {
      re int u=a[i].u,v=a[i].v;
      a[i].tag=(getlca(u,hv)==getlca(v,hv));
      if(a[i].tag) a[i].lca=getlca(u,v);
      else if(dd[getlca(v,hv)]>=dd[getlca(u,hv)]) a[i].gen=u,a[i].lca=v,a[i].lca1=getlca(v,hv);
      else a[i].gen=v,a[i].lca=u,a[i].lca1=getlca(u,hv);
      //printf("%d %d %d %d %d %d\n",u,v,a[i].tag,a[i].lca,getlca(u,hv),getlca(v,hv));
   }
  re int l=0,r=m+100;
  while(l<r)
    {
      re int mid=l+r>>1;
      if(check(mid)) r=mid;
      else l=mid+1;
    }
  if(r==m+100) puts("-1");
  else
    {
      check(r);
      printf("%d\n",r);
      fp(i,1,n) if(vis[i]) printf("%d ",i);
      puts("");
    }
  fclose(stdin);
  fclose(stdout);
  return 0;
}