洛谷1351 联合权值
交题记录
20:47 第1次提交 70'
输入文件无法下载（lg大坑比），下载了输出发现第二问萎了，怀疑是取膜的问题。 20:50 第2次提交 70' 我就笑笑不说话。。。两份代码只差了一句取膜，结果新交的时间空间都变大，然后从AWAAAAAWW变成AWAAAWAAWA 咦，输出爆负了。。。 取了膜的减一个没取膜的是不是会爆负。。。 20:53 第三次提交 AC 把取膜改个位置就A了。。。 是不是边做题编写博客欧气强些。。。 望着dalao们100~200+ms而我88ms我好骄傲。。。 最后吐槽一句这为什么是dp题。。。
题解
第一反应
距离为2的点，只会是两个兄弟，或者一个是另一个的子节点的子节点。
更进一步：兄弟节点情况的优化
父子的很好算。
计算兄弟节点的联合权值？
- \(O(n^2)\)枚举
- 还有啥???
先把\(O(n^2)\)的算法列出来：
for i := 1 to n for j := 1 to n if(i<>j)then {用w[i]*w[j]更新答案} 别问我为什么用Pascal。。。
总之，每一个点都会和其他兄弟配对一次。 所以点\(a\)对答案的贡献为\[ \sum_{i=其他兄弟}w[a]*w[i] \]\[ =w[a]*\sum_{i=其他兄弟}w[i] \]\[ =w[a]*(\sum_{i=包括a的所有兄弟}w[i]-w[a]) \] 于是第二问解决了。。。就在这里取膜失误身败名裂。。。 当然，对于第一问，就是权值最大的两个孩子嘛。。。 现在怎么优化就显而易见了，然后可以过了。Code
// It is made by XZZ#include#include #include using namespace std;#define rep(a,b,c) for(rg int a=b;a<=c;a++)#define drep(a,b,c) for(rg int a=b;a>=c;a--)#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])#define il inline#define rg register#define vd voidtypedef long long ll;il int gi(){ rg int x=0,f=1;rg char ch=getchar(); while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*f;}const int maxn=200100,maxm=maxn<<1;int w[maxn];int fir[maxn],nxt[maxm],dis[maxm],id;il vd add(int a,int b){nxt[++id]=fir[a],fir[a]=id,dis[id]=b;}int Max=0,Sum=0,mod=10007;il vd dfs(int now,int fa,int grandfa){ Max=max(Max,w[now]*w[grandfa]); Sum=(Sum+w[now]*w[grandfa]*2)%mod; int sum=0; erep(i,now)if(dis[i]^fa){ sum+=w[dis[i]]; dfs(dis[i],now,fa); } int max1=0,max2=0; erep(i,now)if(dis[i]^fa){ Sum=(Sum+w[dis[i]]*((sum-w[dis[i]])%mod))%mod; if(w[dis[i]]>max1)max2=max1,max1=w[dis[i]]; else if(w[dis[i]]>max2)max2=w[dis[i]]; } Max=max(Max,max1*max2);}int main(){ int n=gi(),u,v; rep(i,2,n)u=gi(),v=gi(),add(u,v),add(v,u); rep(i,1,n)w[i]=gi(); dfs(1,0,0); printf("%d %d\n",Max,Sum); return 0;}