#1676 : 树上的等差数列
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一棵包含N个节点的无根树，节点编号1~N。其中每个节点都具有一个权值，第i个节点的权值是Ai。
小Hi希望你能找到树上的一条最长路径，满足沿着路径经过的节点的权值序列恰好构成等差数列。
输入
第一行包含一个整数N。
第二行包含N个整数A1, A2, ... AN。
以下N-1行，每行包含两个整数U和V，代表节点U和V之间有一条边相连。
对于50%的数据，1 ≤ N ≤ 1000
对于100%的数据，1 ≤ N ≤ 100000, 0 ≤ Ai ≤ 100000, 1 ≤ U, V ≤ N
输出
最长等差数列路径的长度
样例输入
7
3 2 4 5 6 7 5
1 2
1 3
2 7
3 4
3 5
3 6
样例输出
4
大意：一棵树，每个点有一个权值，求树上连续节点能构成等差数列的最长长度。
题解：这题应该有很多种解法，我学习了其中一种非常简洁的：树形dp
不过状态数很多：f[节点][公差+delta] 肯定是不行的。
但是细想之后，发现状态很稀疏：公差很少，为每一个节点开一个map，当做数组用就行辣。
我的状态是f[i][j] 表示以 i 为序列的一头，公差为 j 的最长长度-1（不包括 i ，此细节无所谓）
需要注意公差为0 时的转移
ps: 话说大早上起来对拍调试真的爽！！emmm现在好像已经中午了（手动滑稽）
/*
Welcome Hacking
Wish You High Rating
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<map>
#include<vector>
using namespace std;
int read(){
int xx=0,ff=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
return xx*ff;
}
inline int mymax(int xx,int yy)
{if(xx>yy)return xx;return yy;}
const int maxn=100010;
int N,lin[maxn],len,v[maxn],ans=1;
struct edge{
int y,next;
}e[maxn<<1];
map<int,int>f[maxn];
inline void insert(int xx,int yy){
e[++len].next=lin[xx];
lin[xx]=len;
e[len].y=yy;
}
void dfs(int x,int fa){
for(int i=lin[x];i;i=e[i].next)
if(e[i].y!=fa){
dfs(e[i].y,x);
int diff=v[e[i].y]-v[x];
if(!diff){
ans=mymax(ans,f[x][0]+f[e[i].y][0]+2);
f[x][0]=mymax(f[x][0],f[e[i].y][0]+1);
}
else{
f[x][diff]=mymax(f[x][diff],f[e[i].y][diff]+1);
ans=mymax(ans,f[x][-diff]+f[x][diff]+1);
}
//printf("%d %d %d\n",x,diff,f[x][diff]);
}
}
int main(){
//freopen("in","r",stdin);
//freopen("out","w",stdout);
N=read();
for(int i=1;i<=N;i++)
v[i]=read();
for(int i=1;i<N;i++){
int t1=read(),t2=read();
insert(t1,t2);
insert(t2,t1);
}
dfs(1,0);
printf("%d\n",ans);
return 0;
}