4.13 BJ集训

佚名 6年前 (2019-04-13) 随笔 1992人围观抢沙发百度已收录

题目大意：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

思路：

T2 transport

题目大意：

一个树上，每个点有权值，边权有权值

求有多少对点对满足对于这条路径任意一个前缀都满足点的权值和>边的权值和

思路：

很明显的点分治，对每个分治重心

搜出每一条从重心开始的链需要之前盈余多少权值才能走到，搜出每一条能走到重心的链到根后盈余多少

（第一个分别记录$dis$的最低值，第二个记录最小的一个后缀判断能否走到

排序后双指针，然后容斥一下即可

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<vector>
 8 #include<queue>
 9 #define rep(i,s,t) for(register int i=(s),i##end=(t);i<=i##end;++i)
10 #define dwn(i,s,t) for(register int i=(s),i##end=(t);i>=i##end;--i)
11 #define ren for(int i=fst[x];i;i=nxt[i])
12 #define ll long long
13 #define inf 2139062143
14 #define MAXN 100100
15 #define MOD 1000000007
16 #define pls(a,b) ((a)+(b))%MOD
17 #define mul(a,b) (1LL*(a)*(b))%MOD
18 using namespace std;
19 inline int read()
20 {
21     int x=0,f=1;char ch=getchar();
22     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
23     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
24     return x*f;
25 }
26 int n,m,v[MAXN],fst[MAXN],nxt[MAXN<<1],to[MAXN<<1],val[MAXN<<1];
27 int mx[MAXN],sz[MAXN],Sum,rt,Mx,vis[MAXN],cnt;
28 void add(int u,int v,int w) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w;}
29 void getrt(int x,int pa)
30 {
31     mx[x]=0,sz[x]=1;ren if(to[i]^pa&&!vis[to[i]])
32         getrt(to[i],x),sz[x]+=sz[to[i]],mx[x]=max(mx[x],sz[to[i]]);
33     mx[x]=max(mx[x],Sum-sz[x]);if(mx[x]<Mx) Mx=mx[x],rt=x;
34 }
35 ll g[MAXN],f[MAXN],ans;int ln,len;
36 void get1(int x,int pa,ll mn,ll dis)
37 {
38     g[++len]=mn,dis+=v[x];ren if(to[i]^pa&&!vis[to[i]])
39         get1(to[i],x,min(dis-val[i],mn),dis-val[i]);
40 }
41 void get2(int x,int pa,ll mx,ll dis)
42 {
43     if(v[x]-mx>=0) f[++ln]=v[x]+dis;mx-=v[x],dis+=v[x];ren if(to[i]^pa&&!vis[to[i]])
44         get2(to[i],x,max((ll)val[i],mx+val[i]),dis-val[i]);
45 }
46 void calc(int x,int w,ll res=0)
47 {
48     int tmp=0,pos=ln;sort(g+1,g+len+1);sort(f+1,f+ln+1);
49     rep(i,1,len) {while(pos&&g[i]+f[pos]>=0) tmp++,pos--;res+=tmp;}ans+=res*w;
50 }
51 void div(int x)
52 {
53     vis[x]=1;ln=len=0;get1(x,0,0,0);get2(x,0,0,-v[x]);
54     calc(x,1);ans--;ren if(!vis[to[i]])
55     {
56         ln=len=0;get1(to[i],x,v[x]-val[i],v[x]-val[i]);
57         get2(to[i],x,val[i],-val[i]);calc(to[i],-1);
58     }
59     ren if(!vis[to[i]]) {Sum=sz[to[i]],Mx=n+1;getrt(to[i],x);div(rt);}
60 }
61 int main()
62 {
63     freopen("transport.in","r",stdin);freopen("transport.out","w",stdout);
64     n=read();int a,b,c;rep(i,1,n) v[i]=read();
65     rep(i,2,n) a=read(),b=read(),c=read(),add(a,b,c),add(b,a,c);
66     Sum=n,Mx=n+1;getrt(1,0);div(rt);printf("%lld\n",ans);
67 }