技巧题

题目传送门

题目意思很简单&＃xff0c;求两个距离为2的点的点权。可以转化为求一个点其中两条出边的点权。

刚开始写DFS&＃xff0c;然后华丽丽地T掉了。。。以为哪里写挂了&＃xff0c;算了一下发现是O(n2)O(n2)的。。。于是重新想算法

后来发现一个公式:2∗(a[1]∗a[2]&＃43;a[2]∗a[3]&＃43;a[1]∗a[3])&＃61;(a[1]&＃43;a[2]&＃43;a[3])2−(a[1]2&＃43;a[2]2&＃43;a[3]2)2∗(a[1]∗a[2]&＃43;a[2]∗a[3]&＃43;a[1]∗a[3])&＃61;(a[1]&＃43;a[2]&＃43;a[3])2−(a[1]2&＃43;a[2]2&＃43;a[3]2)&＃xff0c;
它的拓展式也是成立的。&＃xff08;证明的话展开化简即可&＃xff09;

于是我们只需要遍历一遍就行了&＃xff0c;算值的时候把这个东西代进去。求最大值就是求前二大值的积。

代码&＃xff1a;

#include
#include
#include
#define MAXN 200000
#define DALAO 10007
using namespace std;
typedef long long LL;
struct edge{int next,to;
};
int n,k;
LL sum,ans;
int h[MAXN&＃43;5],w[MAXN&＃43;5];
edge ed[MAXN*2&＃43;5];
inline char readc(){static char buf[100000],*l&＃61;buf,*r&＃61;buf;if (l&＃61;&＃61;r) r&＃61;(l&＃61;buf)&＃43;fread(buf,1,100000,stdin);if (l&＃61;&＃61;r) return EOF; return *l&＃43;&＃43;;
}
inline int _read(){int num&＃61;0; char ch&＃61;readc();while (ch<&＃39;0&＃39;||ch>&＃39;9&＃39;) ch&＃61;readc();while (ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;) { num&＃61;num*10&＃43;ch-48; ch&＃61;readc(); }return num;
}
void addedge(int x,int y){ed[&＃43;&＃43;k].next&＃61;h[x]; ed[k].to&＃61;y; h[x]&＃61;k;
}
void calc(int x){LL s1&＃61;0,s2&＃61;0,t1&＃61;0,t2&＃61;0;for (int i&＃61;h[x];i;i&＃61;ed[i].next){int v&＃61;ed[i].to;s1&＃43;&＃61;w[v]; s2&＃43;&＃61;w[v]*w[v];if (t1else if (w[v]>t2) t2&＃61;w[v];}s1*&＃61;s1; ans&＃61;max(ans,t1*t2); sum&＃61;(((s1-s2)%DALAO&＃43;sum)%DALAO)%DALAO;
}
int main(){n&＃61;_read();for (int i&＃61;1;iint u&＃61;_read(),v&＃61;_read();addedge(u,v); addedge(v,u);}for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) w[i]&＃61;_read();for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) calc(i);printf("%lld %lld\n",ans,sum%DALAO);//其实并不需要long longreturn 0;
}