\(mjt树\)

题目背景

从前森林里有一棵很大的\(mjt\)树，树上有很多小动物。

题目描述

mjt树上有 \(n\) 个房间，第 i 个房间住着\(a_i\) 只第bi 种小动物。
这\(n\)个房间用\(n-1\)条路连接起来，其中房间1位\(mjt\)树的根。
现在每个房间\(x\)的小动物想知道，以房间x为根的\(mjt\)树中有多少只它们的同类.

输入输出格式

输入格式：

第一行一个整数n，表示房间数
接下来\(n\)行，每行两个整数\(a_i,b_i\)。
再之后\(n-1\)行，每行两个整数\(x,y\)，表示x和y之间有一条路径

输出格式：

一行n个数，第\(i\)个数表示以房间i为根的\(mjt\)树中\(b_i\)种小动物有多少只，两个数之间用空格隔开

输入输出样例

输入样例#1：

5
2 1
3 1
4 2
5 1
6 2
1 2
1 3
3 4
3 5

输出样例#1：

10 3 10 5 6

说明

\(b_i\leq n\leq 100000,a_i\leq 1000\)
by xjjppm.

这个题好像是“理责慨”理叔出的
但是为什么叫“焖箭筒”树我还真不知道

我YY了三个做法
有两种做法能A这道题
首先题目将所有点划分成许多种类
所以我用颜色代替

做法1：

DFS中找到每个点所有的与其颜色相同的所有祖先
在祖先中加上这个点的权值
缺陷：太慢

做法2：

将每个点的权值加到其最近的祖先处
然后在回溯的时候就会逐步加到其所有祖先处
查询很快
如果整棵树是比较均衡的树
那么速度就会还不错
缺陷：很容易被卡

做法3：

在DFS的时候处理正在遍历的链上的所有颜色的节点
这样就可以O(1)找出其最近祖先
同样是将权值加到最近祖先处
速度和DFS遍历树的速度差不多
能非常快速的通过该题

做法1

#include<iostream>
#include<cstdio>
#define N 1000005
using namespace std;struct node{int next,v;
}edge[N];
int head[N],sum;void add(int a,int b){edge[++sum].v=b;edge[sum].next=head[a];head[a]=sum;edge[++sum].v=a;edge[sum].next=head[b];head[b]=sum;
}int n;
int fa[N];
int ans[N];
int zhong[N];
int duosh[N];int find(int s){int father=fa[s];while(father){ans[father]+=(zhong[s]==zhong[father])*duosh[s];father=fa[father];}ans[s]+=duosh[s];
}void DFS(int s,int fath){fa[s]=fath;find(s);for(int i=head[s];i;i=edge[i].next){if(edge[i].v==fa[s])continue;DFS(edge[i].v,s);}
}int main(){cin>>n;for(int i=1;i<=n;++i)scanf("%d%d",&duosh[i],&zhong[i]);for(int i=1;i<n;++i){int a,b;scanf("%d%d",&a,&b);add(a,b);}DFS(1,0);for(int i=1;i<=n;++i)cout<<ans[i]<<' ';return 0;
}

做法2

#include<iostream>
#include<cstdio>
#define N 200010
using namespace std;struct node{int next,v;
}edge[N];
int head[N],sum;void add(int a,int b){edge[++sum].v=b;edge[sum].next=head[a];head[a]=sum;edge[++sum].v=a;edge[sum].next=head[b];head[b]=sum;
}int n;
int fa[N];
int ans[N];
int zhong[N];
int duosh[N];int find(int s){int father=fa[s];while(father){if(zhong[s]==zhong[father]){ans[father]+=ans[s];return 0;}father=fa[father];}
}void DFS(int s,int fath){fa[s]=fath;for(int i=head[s];i;i=edge[i].next){if(edge[i].v==fa[s])continue;DFS(edge[i].v,s);}find(s);
}int main(){scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d%d",&duosh[i],&zhong[i]);for(int i=1;i<n;++i){int a,b;scanf("%d%d",&a,&b);add(a,b);}for(int i=1;i<=n;++i)ans[i]=duosh[i];DFS(1,0);for(int i=1;i<=n;++i)printf("%d ",ans[i]);return 0;
}

做法3

#include<iostream>
#include<cstdio>
#define N 1000010
using namespace std;struct node{int next,v;
}edge[N];
int head[N],sum;void add(int a,int b){edge[++sum].v=b;edge[sum].next=head[a];head[a]=sum;edge[++sum].v=a;edge[sum].next=head[b];head[b]=sum;
}int n;
int fa[N];
int ans[N];
int zhong[N];
int duosh[N];int ff[N];//颜色为i的点最后一次出现的位置 
int color[N];void DFS(int s,int fath){fa[s]=fath;int fn=ff[zhong[s]];ff[zhong[s]]=s;for(int i=head[s];i;i=edge[i].next){if(edge[i].v==fa[s])continue;DFS(edge[i].v,s);}ans[fn]+=ans[s];ff[zhong[s]]=fn;
}int main(){scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d%d",&duosh[i],&zhong[i]);for(int i=1;i<n;++i){int a,b;scanf("%d%d",&a,&b);add(a,b);}for(int i=1;i<=n;++i)ans[i]=duosh[i];DFS(1,0);for(int i=1;i<=n;++i)printf("%d ",ans[i]);return 0;
}

转载于:https://www.cnblogs.com/qdscwyy/p/7739228.html