仰望夜空，你就知道，我来自哪里——gfdfy
B. 夜空
题目链接（题面依旧有问题）：http://10.1.6.216/contest/18/problem/108
题目背景
d
是一个喜欢仰望星空的帅气少年，一天晚上，他一如既往地躺在草地上看星星。看着它们有亮的有暗的，不由得突发奇想，想要考考你。
题目描述
d
对每一颗星星赋予了一个亮度wi，并且他将连在一起会更加明亮的星星连在了一起。由于d
想要时刻知道哪个点在一定范围内是最亮的。
简而言之，题意是这样的：给定n
个点，并给出每个点的点权。同时给出n−1条无向边，保证将所有的点连成一棵树。同时有m
次询问，每次询问输入两个点的编号。需要你对于每一次询问，输出两点之间最短路径上的最大点权。
输入格式
第一行输入n,m
，含义如题目描述。
第二行有n
个数，代表n
个点的点权。
后面n−1
行，有n−1次输入，每次输入x,y，意为从x到y
连有一条无向边。
紧接着m
行，有m次输入，每次输入x,y，即m
次询问。
输出格式
每一行对应一次询问输出。
输入输出样例
样例输入1
5 3
1 2 3 4 5
1 2
1 3
2 4
2 5
1 2
1 4
3 5样例输出1
2
4
5样例输入2
10 10
1 1 1 7 8 5 5 7 4 6
1 2
1 3
2 4
1 5
2 6
3 7
3 8
6 9
4 10
6 1
4 7
9 1
2 7
4 7
3 1
7 3
7 8
3 9
3 3
样例输出2
5
7
5
5
7
1
5
7
5
1
样例解释
在第一个样例中，从1
号点到2号点途径1,2，其中最大点权是2。从1号点到4号点途径1,2,4，其中最大点权是4。从3号点到5号点途径1,2,3,5，其中最大点权是5
。
数据范围
对于30
的数据，n≤100,m≤100
。
对于50
的数据，n≤2000,m≤2000
。
对于70
的数据，n≤2000,m≤200000,0<wi≤1000000000
。
对于100
的数据，n≤200000,m≤200000,0<wi≤264。
主要思路：
当时做这道题的时候就觉得这是一个lca，但是我们发现他还要在lca的过程中保存路径上的最大值，正解肯定是先预处理跳跃过程中经过的最大值，然后在询问的时候O(1)求最大值，但是由于本人蒟蒻一只，所以.....很明显的，这种预处理过程我并不会写，所以我就选择一步一步往上跳，每次跳的时候访问这个节点并且求出当前的最大值。每次询问每次lca一遍，最后就可以判断出路径上的最大值。70分~~
很明显的超出时间复杂度了qwq
先展示一下自己的70分代码，然后我们再来分析一下正解的做法，并顺便复习一下lca，如果等我把所有的题目都整理完还有时间，那么我们就一起来做一下出题人推荐的题目（与此题类似，据TA所说这个题目是那道题的简化版，好像只有绿？）
#include<bits/stdc++.h> using namespace std; int n,m; vector<int> v[202000]; int fa[200005]; int dep[200005]; int a[5020000]; void add(int x,int y) { v[x].push_back(y); } void dfs(int x) { for(int i=0;i<v[x].size();i++){ int y=v[x][i]; if(y==fa[x]) continue; fa[y]=x; dep[y]=dep[x]+1; dfs(y); } } int maxn=-999; int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); maxn=max(a[x],a[y]); while(dep[x]>dep[y]) { x=fa[x]; maxn=max(maxn,a[x]); } if(x==y) return maxn; while(x!=y) { x=fa[x]; y=fa[y]; maxn=max(maxn,a[x]); maxn=max(maxn,a[y]); } return maxn; } int x,y; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",a+i); for(int i=1;i<=n-1;i++) { scanf("%d%d",&x,&y); add(x,y); add(y,x); } dep[1]=1; dfs(1); /*for(int j=0;j<=64;j++){ for(int i=1;i<=n;i++){ fa[i][j+1]=fa[fa[i][j]][j]; } }*/ while(m--) { int x,y; scanf("%d%d",&x,&y); printf("%d ",lca(x,y)); } return 0; }
std70：（出题人的70分代码）
可能没有想我这样啥的人用正解（lca）打了70分的暴力qwq
其实对于70分的数据，我们不需要用lca就可以实现
我们n*n预处理所有点之间的最大值，对于每次询问，我们直接O(1)输出答案即可
出题人的代码：（链式前向星存图）
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<queue> #include<ctime> #include<map> #include<vector> using namespace std; typedef unsigned long long ull; inline ull read(){ ull x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } const int N=2005,M=2000005; int n,m,tot; ull w[N],maxx[N][N]; int ver[M],Next[M],head[N],d[N]; bool v[N][N]; queue<int> q; void add(int x,int y){ ver[++tot]=y; Next[tot]=head[x]; head[x]=tot; } void bfs(int a){ maxx[a][a]=w[a]; //maxx[x][y]表示从节点x到节点y路径上的最大值 q.push(a); v[a][a]=1; q.push(a); while(!q.empty()){ int x=q.front(); q.pop(); for(int i=head[x];i;i=Next[i]){ int y=ver[i]; if(v[a][y]) continue; v[a][y]=1; maxx[a][y]=max(maxx[a][x],w[y]); q.push(y); } } } int main() { // freopen("dfy.in","r",stdin); // freopen("dfy.ans","w",stdout); n=read();m=read(); for(int i=1;i<=n;i++){ w[i]=read(); } for(int i=1,x,y;i<=n-1;i++){ x=read();y=read(); add(x,y); add(y,x); } for(int i=1;i<=n;i++){ bfs(i); } for(int i=1,x,y;i<=m;i++){ x=read();y=read(); printf("%llu ",maxx[x][y]); } return 0; }
自己敲的70分正解代码：（vector存图）
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int N=2005,M=2000005; bool vis[N][N]; ull w[N],maxx[N][N]; queue<int> q; vector<int> v[N]; void add(int x,int y) { v[x].push_back(y); } inline ull read(){ ull x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } void bfs(int a) { maxx[a][a]=w[a]; q.push(a); vis[a][a]=1; // q.push(a); while(!q.empty() ) { int x=q.front() ; q.pop() ; for(int i=0;i<v[x].size();i++) { int y=v[x][i]; if(vis[a][y]==1) continue; vis[a][y]=1; maxx[a][y]=max(maxx[a][x],w[y]); q.push(y); } } } int n,m; int main() { n=read();m=read(); for(int i=1;i<=n;i++) w[i]=read(); for(int i=1;i<=n-1;i++) { int x,y; x=read();y=read(); add(x,y); add(y,x); } for(int i=1;i<=n;i++) { bfs(i);//对于每个节点都要预处理它到 //其他所有节点的最大值 } for(int i=1;i<=m;i++) { int x,y; x=read();y=read(); printf("%llu ",maxx[x][y]); } return 0; }
100分正解：
其实在上面就已经说过了，正解就是lca+对点权的预处理。lca相信大家都不陌生（我相信），所以我们就直接从对于点权的预处理开始讲起。其实有了lca的前置知识，我们发现，由于我们是跳跃式进行lca查询的，所以我们也可以按照lca的方式，采取st表的方法对点权进行求解，设置一个变量maxx[x][i]表示节点x的第 2^i 个祖先与它之间的路径最大值，注意断句理解：节点x的，第 2^i 个祖先，与它之间的，路径的，最大值。（是不是感觉好理解了一点？如果 还是不行就建议多读几遍吧~），这样我们就按照lca的方式进行处理就好啦：
maxx[y][j]=max(maxx[y][j-1],maxx[f[y][j-1]][j-1]);
其实这里是采用的st表的方法来求的maxx，好像不是lca？
算了，反正大致就是这个意思了，但是注意这里面还有一些坑点：
数据范围是2^64，但是我们发现及时是unsigned long long也知道(2^64)-1的范围，而且据毒瘤出题人说他出的还是极限数据，所以这肯定会爆空间的，也就是说当输入数据是2^64时，输入数据会变成0（爆数据范围了嘛）。但是由于我们求的又是最大值，肯定要用到max函数，所以这里有一下两种方法：
1.对于0特殊处理（std采用的方法）
2.在输入的时候我们就先对数据进行处理，所有数据都减一，这样数据范围就可以贴合unsigned long long 的数据范围了，然后在最后输出答案的时候再加上1（但是我们发现这样还是要对2^64进行特殊处理qwq）
std100（链式前向星存图+附赠数据一份）：
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<queue> #include<ctime> #include<map> #include<vector> using namespace std; typedef unsigned long long ull; inline ull read(){ ull x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-48;ch=getchar();} return x*f; } const int N=200005,M=400005; int n,m,tot; ull w[N],maxx[N][25]; int ver[M],Next[M],head[N],d[N],f[N][25]; queue<int> q; void add(int x,int y){ ver[++tot]=y; Next[tot]=head[x]; head[x]=tot; } void bfs(){ d[1]=1; q.push(1); while(!q.empty()){ int x=q.front(); q.pop(); for(int i=head[x];i;i=Next[i]){ int y=ver[i]; if(d[y]) continue; d[y]=d[x]+1; f[y][0]=x; if(w[x]==0||w[y]==0) maxx[y][0]=0; else maxx[y][0]=max(w[x],w[y]); for(int j=1;j<=23;j++){ f[y][j]=f[f[y][j-1]][j-1]; } for(int j=1;j<=23;j++){ if(maxx[y][j-1]==0||maxx[f[y][j-1]][j-1]==0) maxx[y][j]=0; else maxx[y][j]=max(maxx[y][j-1],maxx[f[y][j-1]][j-1]); } q.push(y); } } } void lca(int x,int y){ if(d[x]<d[y]) swap(x,y); if(w[x]==0||w[y]==0){ printf("18446744073709551616 "); return; } ull maxn=max(w[x],w[y]); int k=log(d[x]-d[y])/log(2)+1; for(int i=k;i>=0;i--){ if(d[f[x][i]]>=d[y]){ if(maxx[x][i]==0){ maxn=0; break; } maxn=max(maxn,maxx[x][i]); x=f[x][i]; } } if(maxn==0){ printf("18446744073709551616 "); return; } if(x==y){ printf("%llu ",maxn); return; } k=log(d[x])/log(2)+1; for(int i=k;i>=0;i--){ if(f[x][i]!=f[y][i]){ if(maxx[x][i]==0||maxx[y][i]==0){ maxn=0; break; } else{ maxn=max(maxn,max(maxx[x][i],maxx[y][i])); } x=f[x][i]; y=f[y][i]; } } if(maxn==0){ printf("18446744073709551616 "); return; } if(maxx[x][0]==0||maxx[y][0]==0){ maxn=0; } else{ maxn=max(maxn,max(maxx[x][0],maxx[y][0])); } if(maxn==0){ printf("18446744073709551616 "); return; } else{ printf("%llu ",maxn); } } int main() { // freopen("dfy8.in","r",stdin); // freopen("dfy8.out","w",stdout); for(int i=0;i<=N-2;i++){ for(int j=0;j<=23;j++){ maxx[i][j]=1; } } n=read();m=read(); for(int i=1;i<=n;i++){ w[i]=read(); } // for(int i=1;i<=n;i++){ // printf("%llu ",w[i]); // } // printf(" "); for(int i=1,x,y;i<=n-1;i++){ x=read();y=read(); add(x,y); add(y,x); } bfs(); // for(int i=1;i<=n;i++){ // for(int j=0;j<=3;j++){ // printf("%llu ",maxx[i][j]); // } // printf(" "); // } // for(int i=1;i<=n;i++){ // printf("%llu ",d[i]); // } // printf(" "); for(int i=1,x,y;i<=m;i++){ x=read();y=read(); if(x==y){ if(w[x]==0){ printf("18446744073709551616 "); } else{ printf("%llu ",w[x]); } } else lca(x,y); } return 0; } /* 5 10 18446744073709551616 2 3 4 5 1 2 1 3 2 4 2 5 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5 */
自己敲的代码：(vector存图)：
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; typedef unsigned long long ull; inline ull read() { ull x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)) { x=x*10+ch-48; ch=getchar(); } return x*f; } const int N=200005,M=400005; int n,m,d[N]; ull w[N],maxx[N][25]; vector<int> v[N]; queue<int> q; int f[N][25]; void bfs() { d[1]=1;//因为树上所有节点我们都是要遍历一遍的， //所以选取哪个点作为起点都是可以的 // int y; q.push(1); while(!q.empty() ) { int x=q.front() ; q.pop() ; for(int i=0; i<v[x].size() ; i++) { int y=v[x][i]; if(d[y]) continue; d[y]=d[x]+1; f[y][0]=x; if(w[x]==0||w[y]==0) maxx[y][0]=0; else maxx[y][0]=max(w[x],w[y]); for(int j=1; j<=23; j++) { f[y][j]=f[f[y][j-1]][j-1]; } for(int j=1; j<=23; j++) { if(maxx[y][j-1]==0||maxx[f[y][j-1]][j-1]==0) maxx[y][j]=0; else maxx[y][j]=max(maxx[y][j-1],maxx[f[y][j-1]][j-1]); } q.push(y); } } } void add(int x,int y) { v[x].push_back(y); } void lca(int x,int y) { // cout<<x<<" "<<y<<" :"<<endl; if(d[x]<d[y]) swap(x,y); if(w[x]==0||w[y]==0) { printf("18446744073709551616 "); return ; } ull maxn=max(w[x],w[y]); // cout<<maxn<<" 1"<<endl; int k=log(d[x]-d[y])/log(2)+1; for(int i=k; i>=0; i--) { if(d[f[x][i]]>=d[y]) {//1.需要取等！！！我调了好长时间才发现这个bug if(maxx[x][i]==0) { maxn=0; // cout<<maxn<<" 2"<<endl; break; } maxn=max(maxn,maxx[x][i]); // cout<<maxn<<" 3"<<endl; // cout<<"x: "<<x<<endl; x=f[x][i]; // cout<<x<<" **** "<<endl; } } // cout<<"x: "<<x<<" "<<"y: "<<y<<endl; // cout<<maxn<<" 4"<<endl; if(maxn==0) { printf("18446744073709551616 "); return; } // cout<<maxn<<endl; if(x==y) { printf("%llu ",maxn); return; } k=log(d[x])/log(2)+1; for(int i=k;i>=0;i--) { if(f[x][i]!=f[y][i]){ if(maxx[x][i]==0||maxx[y][i]==0){ maxn=0; // cout<<maxn<<" 5"<<endl; break; } else { maxn=max(maxn,max(maxx[x][i],maxx[y][i])); // cout<<maxn<<" 6"<<endl; } x=f[x][i]; y=f[y][i]; } } if(maxn==0) { printf("18446744073709551616 "); return ; } // cout<<maxn<<" maxn"<<endl; if(maxx[x][0]==0||maxx[y][0]==0) { printf("18446744073709551616 "); return; } else { maxn=max(maxn,max(maxx[x][0],maxx[y][0])); } if(maxn==0) { printf("18446744073709551616 "); return; } else printf("%llu ",maxn); } int main() { for(int i=0;i<=N-2;i++){ for(int j=0;j<=23;j++){ maxx[i][j]=1; } } n=read(); m=read(); for(int i=1; i<=n; i++) w[i]=read(); for(int i=1; i<=n-1; i++) { int x,y; x=read(); y=read(); add(x,y); add(y,x); } bfs(); /*int k=24; for(int i=1;i<=n;i++) { for(int j=0;j<=k;j++) cout<<maxx[i][j]<<" "; cout<<endl; } cout<<endl; k=24; for(int i=1;i<=n;i++) { for(int j=0;j<=k;j++) cout<<f[i][j]<<" "; cout<<endl; }*/ for(int i=1; i<=m; i++) { int x,y; x=read(); y=read(); if(x==y) { if(w[x]==0) printf("18446744073709551616 ");//2.一开始这里的==写成=了，调了20min qwq else printf("%llu ",w[x]); // cout<<w[x]<<endl; } else lca(x,y); } return 0; }
不行不行，这个题太恶心了，我写了一个多小时，调了一个多小时，终于AC了qwq
长代码出现错误真的太致命了，写的时候一定一定要小心仔细!!不然最后找到哪里出错都是问题qwq
-----------end-----------