树上问题入门
结点、叶结点、分支结点、儿子结点
有根树，无根树
子孙、祖先、兄弟结点
结点的度，结点的层次，树的度，树的深度
森林，仙人掌，沙漠
树的存储
树的遍历
结点的父亲，树的深度，树上距离，树的子树大小，树的最大子树，子树的最长链（以子树的根为一个端点，叶为另一个端点），子树最大权，次长链
公共祖先，最近公共祖先
链的长度
树的直径
树的重心
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
#include<algorithm> #include<cstdio> #include<iostream> #include<vector> #define mp(x,y) make_pair(x,y) #define ft first #define sd second #define pa pair<int,int> #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int val[100005]; int fa[100005],dep[100005],size[100005],mx_size[100005],len[100005],len2[100005],mx[100005]; vector<int>v[100005]; int n; void dfs(int x) { printf("%d ",x); for (int i=0;i<v[x].size();i++) dfs(v[x][i]); } void getfa(int x) { for (int i=0;i<v[x].size();i++) { fa[v[x][i]]=x; getfa(v[x][i]); } } void getdep(int x) { for (int i=0;i<v[x].size();i++) { dep[v[x][i]]=dep[x]+1; getdep(v[x][i]); } } int getdis(int x,int y) { if(x==y)return 0; if(dep[x]==dep[y])return getdis(fa[x],fa[y])+2; if(dep[x]>dep[y])return getdis(fa[x],y)+1; return getdis(x,fa[y])+1; } void getsize(int x) { size[x]=1; for (int i=0;i<v[x].size();i++) { getsize(v[x][i]); size[x]+=size[v[x][i]]; mx_size[x]=max(mx_size[x],size[v[x][i]]); } } void getlen(int x) { for(int i=0;i<v[x].size();i++) { getlen(v[x][i]); len[x]=max(len[x],len[v[x][i]]+1); len2[x]=max(len2[x],len[v[x][i]]+1+len[x]); } } void getmx(int x) { mx[x]=val[x]; for(int i=0;i<v[x].size();i++) { getmx(v[x][i]); mx[x]=max(mx[x],mx[v[x][i]]); } } int main() { n=read(); for(int i=1;i<=n;i++) val[i]=read(); for(int i=1;i<n;i++) { int x=read(),y=read(); v[x].push_back(y); } return 0; } |
Subscribe
计数器 9855856
OI 课件=>
OI 课件=>