F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 3631 >> 求助啊,为什么一直RE
taxxxx @ 2017-10-28 17:02:45
[ Quote ] [ Edit ] [ Delete ] 1#
#include<iostream>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<string>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
struct node{
int to,next;
}edge[600060];
int n,a[300030],f[300030],first[300030],dep[300030],fa[300030][20],cnt;
int read()
{
register int x=0;
register char ch;
for(ch=getchar();!isdigit(ch);ch=getchar());
for(;isdigit(ch);ch=getchar())
x=(x<<1)+(x<<3)+ch-'0';
return x;
}
void add(int x,int y)
{
edge[++cnt].to=y;
edge[cnt].next=first[x];
first[x]=cnt;
}
void dfs(int x)
{
for(int i=first[x];i;i=edge[i].next)
{
if(edge[i].to!=fa[x][0])
{
dep[edge[i].to]=dep[x]+1;
fa[edge[i].to][0]=x;
dfs(edge[i].to);
}
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
int will=dep[x]-dep[y];
for(int step=0;will;step++,will>>=1)
{
if(will&1) x=fa[x][step];
}
if(x==y) return x;
for(int i=18;i>=0;--i)
{
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
void dp(int x)
{
for(int i=first[x];i;i=edge[i].next)
{
if(edge[i].to!=fa[x][0])
{
dp(edge[i].to);
f[x]+=f[edge[i].to];
}
}
}
int main()
{
int _q=10<<20;
char *_p=(char*)malloc(_q)+_q;
__asm__("movl %0, %%esp\n"::"r"(_p));
ios::sync_with_stdio(false);
cout.tie(NULL);
n=read();
for(int i=1;i<=n;++i)
a[i]=read();
int x,y;
for(int i=1;i<=n-1;++i)
{
x=read();
y=read();
add(x,y);
add(y,x);
}
dfs(a[1]);
for(int i=1;i<=18;++i)
for(int j=1;j<=n;++j)
if(fa[j][i-1]) fa[j][i]=fa[fa[j][i-1]][i-1];
for(int i=1;i<n;++i)
{
int t=lca(a[i],a[i+1]);
f[a[i]]++;
f[a[i+1]]++;
f[fa[t][0]]--;
f[t]--;
}
dp(a[1]);
for(int i=2;i<=n;++i) f[a[i]]--;
for(int i=1;i<=n;++i)
cout<<f[i]<<endl;
return 0;
}
taxxxx @ 2017-10-29 15:02:52
[ Quote ] [ Edit ] [ Delete ] 2#
自回:不能用cout?
[Top] [Previous Page] [Next Page]

HOME Back