喜欢的话就坚持吧

9月 18

5.00 avg. rating (96% score) - 1 vote

题目大意

给你一棵树,他会给你指定一个到达每个点的顺序,问每个点被经过了几次。最后到的那个点不算次数。


一读题就发现这是道裸的让你求树上点被路径覆盖次数。
直接树上对点差分就好了。
对于x,y两点
val[x]+ 1,val[y]+1
val[lca(x,y)]-1,val[fa[(lca(x,y)]-1

然后dfs一遍就行了。
(tarjan求lca不知道比倍增高明到哪去了)
(树剖:“???”)

还有一个细节,a_2 – a_n被重复计算,最后减去1即可。

#include <cstdio>
#include <algorithm>
#include <vector>

//#define int long long
using namespace std;
const int N=300005;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
char buf[(1 << 22)], *p1 = buf, *p2 = buf;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
struct data
{
    int v,nxt;
}edge[N<<1];
int alist[N],cnt;
vector<int> query[N],query_id[N];
inline void add(int u,int v){edge[++cnt]=(data){v,alist[u]},alist[u]=cnt;}
inline void add_query(int x,int y,int id)
{
    query[x].push_back(y);query_id[x].push_back(id);
    query[y].push_back(x);query_id[y].push_back(id);
}
int n,a[N];

struct bcj
{
    int fa[N+5];
    inline void be(){for(int i=1;i<=N;++i) fa[i]=i;}
    inline int find(int x){return fa[x]=x==fa[x]?x:find(fa[x]);}
}s;


int vis[N],fa[N],lca[N];
inline void tarjan(int x)
{
    vis[x]=1;
    for(int i=alist[x];i;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(vis[v]) continue;fa[v]=x;
        tarjan(v);
        s.fa[v]=x;
    }
    for(int i=0;i<query[x].size();++i)
    {
        int v=query[x][i],id=query_id[x][i];
        if(vis[v]==2)
        {
            lca[id]=s.find(v);
        }
    }
    vis[x]=2;
}

int val[N],ans[N];
inline void dfs(int x)
{
    ans[x]+=val[x];
    for(int i=alist[x];i;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(v==fa[x]) continue;
        dfs(v);
        //ch[r]+=ch[xx];//???? 
        ans[x]+=ans[v];
    }
}
signed main()
{
//  freopen("wtf.txt","r",stdin);
//  freopen("qqq.out","w",stdout);
    //scanf("%d",&n);
    n=read();
    for(int i=1;i<=n;++i) a[i]=read();s.be();
    for(int i=1,x,y;i<n;++i)
    {
        x=read();y=read();
        //scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
        add_query(a[i],a[i+1],i);
    }
    tarjan(1);
    for(int i=1;i<n;++i)
    {
        val[a[i]]++;val[a[i+1]]++;
        val[lca[i]]--;val[fa[lca[i]]]--;
    }
//  for(int i=1;i<=n;++i) printf("%d ",val[i]);printf("\n");
    dfs(1);
    for(int i=2;i<=n;++i) ans[a[i]]--;
    //printf("%lld\n",ans[1]);
    for(int i=1;i<=n;++i) //if(ans[i]==0) printf("%lld\n",ans[i]);
     printf("%d\n",ans[i]);
} 
5.00 avg. rating (96% score) - 1 vote
  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

活捉 2 条