NC20139. [JLOI2014]松鼠的新家
描述
输入描述
第一行一个整数n，表示房间个数第二行n个整数，依次描述a1-an接下来n-1行，每行两个整数x，y，表示标号x和y的两个房间之间有树枝相连。
输出描述
一共n行，第i行输出标号为i的房间至少需要放多少个糖果，才能让维尼有糖果吃。
示例1
输入:
5 1 4 5 3 2 1 2 2 4 2 3 4 5
输出:
1 2 1 2 1
C++(g++ 7.5.0) 解法, 执行用时: 379ms, 内存消耗: 50088K, 提交时间: 2022-08-11 18:26:33
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;cin>>n;
vector<int> a(n+1),sz(n+1),fa(n+1),son(n+1),top(n+1),dep(n+1),s(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
vector<vector<int>> node(n+1);
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
node[u].push_back(v);
node[v].push_back(u);
}
function<void(int,int)> dfs1=[&](int u,int v)->void{
sz[u]=1;fa[u]=v;
dep[u]=dep[v]+1;
for(int x:node[u])if(x!=v){
dfs1(x,u);
sz[u]+=sz[x];
if(sz[x]>sz[son[u]])son[u]=x;
}
};
function<void(int,int)> dfs2=[&](int u,int to)->void{
top[u]=to;
if(son[u]){
dfs2(son[u],to);
for(int x:node[u])if(x!=son[u]&&x!=fa[u])
dfs2(x,x);
}
};
function<int(int,int)> lca=[&](int u,int v)->int{
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=fa[top[u]];
}
return dep[u]>dep[v]?v:u;
};
dfs1(1,0);
dfs2(1,1);
for(int i=2;i<=n;i++){
int u=a[i-1],v=a[i],f=lca(u,v);
s[u]++,s[v]++,s[f]--,s[fa[f]]--;
}
function<void(int,int)> dfs3=[&](int u,int v)->void{
for(int x:node[u])if(x!=v)dfs3(x,u),s[u]+=s[x];
};
dfs3(1,0);
for(int i=2;i<=n;i++)s[a[i]]--;
for(int i=1;i<=n;i++)
cout<<s[i]<<"\n";
}
C++(clang++ 11.0.1) 解法, 执行用时: 615ms, 内存消耗: 120524K, 提交时间: 2022-09-28 22:43:07
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+50;
vector<int>e[N];
int n,a[N];
int dep[N],fa[N][30];
void dfs(int u,int lst){
dep[u]=dep[lst]+1;
fa[u][0]=lst;
for(int i=1;i<=20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
for(auto v:e[u])
if(v!=lst)
dfs(v,u);
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;~i;i--)
if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
if(x==y) return y;
for(int i=20;~i;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int f[N];
void get(int u,int lst){
for(auto v:e[u])
if(v!=lst)
get (v,u),f[u]+=f[v];
}
signed main(void){
ios::sync_with_stdio(false);cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<n;i++){
int l=lca(a[i],a[i+1]);
f[a[i]]++;
f[a[i+1]]++;
f[l]--;
f[fa[l][0]]--;
}
get(1,0);
for(int i=2;i<=n;i++) f[a[i]]--;
for(int i=1;i<=n;i++) cout<<f[i]<<"\n";
return 0;
}