noip2016 天天爱跑步

没看过正解。。应该是些乱七八糟想不出来的东西

解法1：

首先，必须要做的是将每条路径拆成2个直的路径

那么对于那条从深度大的到深度小的路径 dep[x]-dep[y]应该等于观察时间

那么就可以在这些点打标记

那问题在于怎么找这些点

可以把深度为x的数组用vector搞出来

然后每次判断一下x里面的元素是否在他的子树中（判断一下lca就好了）

树剖判断一下每个点的覆盖次数

对于另一条路径同理做

代码：

解法2：

这个解法复杂度是可以分析出来的

首先还是把路径拆成两条

那么对于那条从深度大的到深度小的路径

考虑启发式合并

对于每个点维护一颗splay表示子树中出现的dep值的个数

将路径顶端和底端分别在该点打标记

访问到顶端时删除底端时插入

由于每一次向上会导致所有元素的权值变化所以可以加一个标记（插入时减掉这个值）

那么到查询点的时候就在splay上查询就可以了

那么复杂度是nlogn*splay的复杂度也就是nlog^2n 不过splay的常数感觉这方法还是很虚啊。。。

还有就是splay的insert操作之后要splay一下

防止是这颗树的第一个节点

代码：

#include <bits/stdc++.h>

using namespace std;

#define maxn 6200000

#define maxn2 310000

int count2[maxn],leftson[maxn],rightson[maxn],fa[maxn],root[maxn2];

struct re{

  int a,b,c;

}a[maxn2*];

int ans[maxn2],bz[maxn2][],dep[maxn2],vw[maxn2],head[maxn2],l,last[maxn2];

int hf[maxn2],cc[maxn2],dd[maxn2],lcaa[maxn2],num[maxn],num2,data[maxn];

int n,m;

vector<int> ve[maxn];

inline void updata(int x)

{

  count2[x]=count2[leftson[x]]+count2[rightson[x]]+;

}

inline void rotate(int x,int y)

{

  int father=fa[x];

  if (y==)

  {

    rightson[father]=leftson[x];

    if (leftson[x]) fa[leftson[x]]=father;

  } else

  {

    leftson[father]=rightson[x];

    if (rightson[x]) fa[rightson[x]]=father;

  }

  fa[x]=fa[father];

  if (fa[father])

  {

    if (leftson[fa[father]]==father) leftson[fa[father]]=x;

    else rightson[fa[father]]=x;

  }

  fa[father]=x;

  if (y==) leftson[x]=father; else rightson[x]=father;

  updata(father); updata(x);

}

inline void splay(int k,int x,int goal)

{

  if (x==root[k]) return;

  int father=fa[x];

  while (father!=goal)

  {

    if (fa[father]==goal)

    {

      if (x==leftson[father]) rotate(x,); else rotate(x,);

    } else

    {

      if (father==leftson[fa[father]])

      {

        if (x==leftson[father]) rotate(father,),rotate(x,);

        else rotate(x,),rotate(x,);

      } else

      {

        if (x==rightson[father]) rotate(father,),rotate(x,);

        else rotate(x,),rotate(x,);

      }

    }

    father=fa[x];

  }

  if (goal==) root[k]=x;

}

inline void dfs(int x,int y)

{

  bz[x][]=y; dep[x]=dep[y]+;

  int u=head[x];

  while (u)

  {

    int v=a[u].b;

    if (v!=y) dfs(v,x);

    u=a[u].a;

  }

}

inline int get_lca(int x,int y)

{

   if (dep[x]<dep[y]) swap(x,y);

   for (int i=;i>=;i--)

     if (dep[bz[x][i]]>=dep[y]) x=bz[x][i];

   if (x==y) return(x);

   for (int i=;i>=;i--)

     if (bz[x][i]!=bz[y][i])

     {

       x=bz[x][i],y=bz[y][i];

     }

   return(bz[x][]);

}

inline void arr(int x,int y)

{

  a[++l].a=head[x];

  a[l].b=y;

  head[x]=l;

}

inline void insert(int x,int v,int w)

{

  int tmp=x;x=root[x];

  while (x)

  {

    if (data[x]==v) break;

    count2[x]++;

    if (v<data[x])

    {

      if (!leftson[x]) break;

      x=leftson[x];

    } else

    {

      if (!rightson[x]) break;

      x=rightson[x];

    }

  }

  if (x!=&&data[x]==v) num[x]+=w; else

  {

    data[++num2]=v; count2[num2]=; fa[num2]=x;

    num[num2]=w;

    if (x!=)

    {

      if (v>data[x]) rightson[x]=num2;

      else leftson[x]=num2;

    }

    splay(tmp,num2,);

  }

}

inline void delete1(int k)

{

  int x=leftson[root[k]];

  if (x==)

  {

    root[k]=rightson[root[k]]; fa[root[k]]=; return;

  }

  while (rightson[x]) x=rightson[x];

  splay(k,x,root[k]);

  rightson[x]=rightson[root[k]];

  if (rightson[root[k]]) fa[rightson[root[k]]]=x;

  updata(x);

  fa[x]=; root[k]=x;

}

inline int search(int x,int goal)

{

  x=root[x];

  while ()

  {

    if (data[x]==goal) return(x);

    if (data[x]<goal)

    {

       if (!rightson[x]) return(x);

       x=rightson[x];

    }

    else

    {

       if (!leftson[x]) return(x);

       x=leftson[x];

    }

  }

}

inline void merge(int x,int y,int z)

{

  while (root[x])

  {

    int tmp=data[root[x]]-last[y]+last[x];

    int o=search(y,tmp);

    if (o!=&&data[o]==tmp) num[o]+=num[root[x]];

    else insert(y,tmp,num[root[x]]);

    delete1(x);

  }

  root[z]=root[y]; last[z]=last[y];

}

inline void dfs2(int x,int fa,int lq)

{

  int u=head[x],pp=ve[x].size();

  for (int i=;i<=pp/-;i++)

  if (!ve[x][i*+])

  {

      insert(x,ve[x][i*],);

  }

  while (u)

  {

    int v=a[u].b;

    if (v!=fa)

    {

       dfs2(v,x,lq);

       last[v]+=lq;

       if (count2[root[x]]<count2[root[v]]) merge(x,v,x);

       else merge(v,x,x);

    }

    u=a[u].a;

  }

  int tmp=search(x,vw[x]-last[x]);

  if (data[tmp]==vw[x]-last[x]) ans[x]+=num[tmp];

  for (int i=;i<=pp/-;i++)

  if (ve[x][i*+])

  {

      int tmp=search(x,ve[x][i*]-last[x]);

      if (num[tmp]>) num[tmp]--;

      else

      {

        splay(x,tmp,);

         delete1(x);

      }

  }

}

int main()

{

  freopen("noip.in","r",stdin);

  freopen("noip.out","w",stdout);

  std::ios::sync_with_stdio(false);

  cin>>n>>m;

  int c,d;

  for (int i=;i<=n-;i++)

    cin>>c>>d,arr(c,d),arr(d,c);

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

    cin>>vw[i];

  dfs(,);

  for (int i=;i<=;i++)

    for (int j=;j<=n;j++)

      bz[j][i]=bz[bz[j][i-]][i-];

  for (int i=;i<=m;i++)

  {

    cin>>c>>d;

    cc[i]=c; dd[i]=d;

    int w=get_lca(c,d);

    lcaa[i]=w;

    hf[i]=dep[c]-dep[w];

  }

  for (int i=;i<=m;i++)

  {

    ve[cc[i]].push_back(); ve[cc[i]].push_back();

    ve[lcaa[i]].push_back(hf[i]); ve[lcaa[i]].push_back();

  }

  dfs2(,,);

  memset(leftson,,sizeof(leftson));

  memset(rightson,,sizeof(rightson));

  memset(num,,sizeof(num));

  memset(count2,,sizeof(count2));

  memset(fa,,sizeof(fa));

  memset(root,,sizeof(root));

  memset(last,,sizeof(last)); num2=;

  memset(data,,sizeof(data));

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

  {

    vector<int> tmp; swap(tmp,ve[i]);

   // ve[i].clear();

  }

  for (int i=;i<=m;i++)

  {

    ve[dd[i]].push_back(hf[i]+dep[dd[i]]-dep[lcaa[i]]);

    ve[dd[i]].push_back();

    ve[lcaa[i]].push_back(hf[i]);

    ve[lcaa[i]].push_back();

  }

  dfs2(,,-);

  for (int i=;i<=m;i++)

  {

    if (hf[i]==vw[lcaa[i]]) ans[lcaa[i]]--;

  }

  for (int i=;i<=n-;i++) cout<<ans[i]<<" ";

  cout<<ans[n];

  return ;

}

巴特西

noip2016 天天爱跑步

最新文章

热门文章