考中:
*********************************************************************************************************************************************************
8点多一点，看完了前两道，没什么思路，看了一眼第三道，这么简单，绝对全场切（不是），9点多一点，写完A了，很高兴，看了看第四题，不会，打了个20的暴力，走了，到了t5,哦吼，有一道水题（不是），思考了一下，11点打完，过了第一个样例，躲不起第二个，手推了一遍，发现样例错了？？？，问了问zyz,他也错了，问了问wyd,他还没看，于是问了问jyh,他说没错，于是我认为可能是不加起点，于是重构了代码，13点过了样例还是不对？？？0分？？？于是打暴力，我*******，还是不对？？？于是去看别的题了，很好，还是都不会，看了看t2,搞了一下，感觉还行，但是不想放弃t5,于是随便写了个dp交了，才5分，也不知道哪错了，于是又打了个暴力10分，于是问zyz题意，又回去打暴力，几发WA以后，终于有了20分，太伤心了，想了想100分，发现我不会了，呜呜呜，回去看t2,只有30分钟了，好伤心，t2也来不及了，随便调了调t2的dp,还是10分，就不管了，最后10分钟，看看手机信息，就这样吧。
总结：非常恶心的是，t5我折腾了2个多小时还是没有搞清题意，题目差评，5星差评。
看完题面以后，一定要把所有的比较小的样例手推一遍。
不会真的可以去上厕所
题解:
t1: 像个模拟，f[i]是1-->i是否全部配对，枚举j判断
l,r是否合法，考虑4种情况
t2:dp
枚举平均数x，f[i][j]就是用前i个数拼成j的方案数，f[i][j]=f[i-1][j]+f[i-1][j-i]+f[i-1][j-2*i]……+f[i-1][j-m*i],最多取m个
x可以随便取，然后数字就被分成了两部分，1,2,……x-1 和 x+1,x+2……n 这些数的贡献实际上可以认为是1,2,……x-1 和 1,2……n-x，预处理一下就可以了
t3:太水了
t4:
推一下式子+线性筛求莫比乌斯函数
另一种写法，明天吧，还没写呢
t5:
回来填坑了
先放代码，感谢对拍，感谢随机数据生成器，感谢题解，感谢ccf，感谢cctv，感谢……
AC来的如此措不及防
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; typedef long long ll; const ll inf=0x3f3f3f3f3f3f3f3f; int tot; int head[N],to[N*2],next1[N*2],val[N*2]; void lian(int x,int y,int v) { to[++tot]=y; next1[tot]=head[x]; head[x]=tot; val[tot]=v; } int w[N]; int vis[N],fq[N],siz[N],mx[N]; int qg[N]; int get_root(int s) { int hh=1,tt=1; fq[s]=0; qg[1]=s; while(hh<=tt) { int x=qg[hh]; hh++; siz[x]=1,mx[x]=0; for(int i=head[x];i;i=next1[i]) { int v=to[i]; if(vis[v]||v==fq[x]) continue; fq[v]=x; qg[++tt]=v; } } int cnt=tt,ma=tt,root=s; while(tt) { int x=qg[tt]; tt--; mx[x]=max(mx[x],cnt-mx[x]); if(mx[x]<ma) ma=mx[x],root=x; siz[fq[x]]+=siz[x]; if(siz[x]>mx[fq[x]]) mx[fq[x]]=siz[x]; } return root; } ll d_f[N],d_g[N];//f是提供多少油，g是还需要多少油 int cnt_f,cnt_g; void dfs(int x,int fa,ll dist,ll f,ll g,int dy) { if(f==0) d_f[++cnt_f]=dist; d_g[++cnt_g]=-g; for(int i=head[x];i;i=next1[i]) { int v=to[i]; if(v==fa||vis[v]) continue;//vis[v]=1 dfs(v,x,dist-val[i]+w[v],min(0ll,f-val[i]+w[v]),min(g,dist-val[i]-dy),dy); }//f-val[i]+w[v],补了以前的空缺才能被统计,g是前缀最小值 } ll ans; void sol(int x) { x=get_root(x); vis[x]=1; cnt_g=0; cnt_f=1; d_f[1]=w[x]; // cout<<x<<" "<<ans<<" "; for(int i=head[x];i;i=next1[i]) { int v=to[i]; if(!vis[v]) { int lf=cnt_f+1,lg=cnt_g+1; dfs(v,x,w[x]-val[i]+w[v],min(w[v]-val[i],0),-val[i],w[x]); if(lf<=cnt_f&&lg<=cnt_g) { sort(d_f+lf,d_f+cnt_f+1); sort(d_g+lg,d_g+cnt_g+1); int r=lg; for(int i=lf;i<=cnt_f;i++) { while(r<=cnt_g&&d_f[i]>=d_g[r]) r++; ans-=r-lg; } } } } sort(d_f+1,d_f+cnt_f+1); sort(d_g+1,d_g+cnt_g+1); int r=1; for(int i=1;i<=cnt_f;i++) { while(r<=cnt_g&&d_f[i]>=d_g[r]) r++; ans+=r-1;//-1 } ans+=cnt_f-1;//cnt_f-1,g的已经在它当做f的时候统计过了 for(int i=head[x];i;i=next1[i]) { int v=to[i]; if(!vis[v]) sol(v); } } int main() { int n; cin>>n; for(int i=1;i<=n;i++) scanf("%d",&w[i]); int x,y,v; for(int i=1;i<=n-1;i++) { scanf("%d %d %d",&x,&y,&v); lian(x,y,v),lian(y,x,v); } sol(1); cout<<ans; return 0; }