C++14(g++5.4) 解法, 执行用时: 1338ms, 内存消耗: 212184K, 提交时间: 2019-04-28 12:44:42

#include<bits/stdc++.h>
#define N 100001
#define M N*200
#define r1 (p<<1)
#define r2 (p<<1|1)
#define mid ((l+r)>>1)
using namespace std;

inline bool rd(int &X)
{
    scanf("%d",&X);return 1;
}

int n,m,ans,tot,num;
struct nd{int nxt,to;}e[N];
int a[N],b[N],c[N],B[N],f[N];
int rt[N<<2],mx[M],ls[M],rs[M];
int head[N],cnt,p[N],po[N],sz[N];
#define For(x) for(int y,i=head[x];(y=e[i].to);i=e[i].nxt)

void add(int x,int y){
    e[++cnt]=(nd){head[x],y};head[x]=cnt;
}
bool cmp(int x,int y){
    return a[x]==a[y] ?  po[x]<po[y] : a[x]<a[y];
}
void dfs(int x){
    sz[x]=1; For(x) dfs(y),sz[x]+=sz[y]; po[x]=++tot;
}
void ins(int &p,int x,int d,int l=1,int r=m){
    if(!p) p=++num; mx[p]=max(mx[p],d);if(l==r) return ;
    x<=mid ? ins(ls[p],x,d,l,mid) : ins(rs[p],x,d,mid+1,r);
}
int ask(int p,int x,int l=1,int r=m){
    if(!p or l==r) return mx[p];
    return x<=mid ? ask(ls[p],x,l,mid) : max(ask(rs[p],x,mid+1,r),mx[ls[p]]);
}
void INS(int p,int x,int d,int v,int l=1,int r=n){
    ins(rt[p],d,v); if(l==r) return ;
    x<=mid ? INS(r1,x,d,v,l,mid) : INS(r2,x,d,v,mid+1,r);
}
int ASK(int p,int L,int R,int v,int l=1,int r=n,int mx=0){
    if(L<=l and r<=R) return ask(rt[p],v);
    if(L<=mid) mx=max(mx,ASK(r1,L,R,v,l,mid));
    if(R >mid) mx=max(mx,ASK(r2,L,R,v,mid+1,r));
    return mx;
}
void work(){
    sort(p+1,p+1+n,cmp);
    for(int x,i=1;i<=n;i++){
        x=p[i];f[x]=ASK(1,po[x]-sz[x]+1,po[x],b[x])+c[x];
        INS(1,po[x],b[x],f[x]); ans=max(ans,f[x]);
    }
}
signed main()
{
    for(int i=rd(n);i<=n;i++)
        rd(a[i]),rd(b[i]),rd(c[i]),B[i]=b[i];
    sort(B+1,B+1+n);m=unique(B+1,B+1+n)-B-1;
    for(int i=1;i<=n;i++)
        b[i]=lower_bound(B+1,B+1+m,b[i])-B,p[i]=i;
    for(int x,y,i=1;i<n;i++)
        rd(x),rd(y),add(x,y);
    dfs(1); work(); cout<<ans;
}

C++11(clang++ 3.9) 解法, 执行用时: 714ms, 内存消耗: 13668K, 提交时间: 2019-04-27 04:13:21

#include<bits/stdc++.h>
#define lson (rt<<1)
#define rson (rt<<1|1)
using namespace std;const int N=1e5+7;
struct data{int to,next;}e[N];struct node{int a,b,c,l,r,ans;}s[N];int mx[N<<2],L[N],R[N],x,y,a[N],b[N],c[N],ans,ind,cnt,head[N],n,m,i,j;
void ins(int u,int v){e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}
bool cmp(node a,node b){return a.a==b.a?(a.b==b.b?a.l>b.l:a.b<b.b):a.a<b.a;}
bool cmp1(node a,node b){return a.b==b.b?(a.a==b.a?a.l>b.l:a.a<b.a):a.b<b.b;}
void dfs(int x){L[x]=++ind;for(int i=head[x];i;i=e[i].next)dfs(e[i].to);R[x]=ind;}
void modify(int rt,int l,int r,int pos,int val){
	mx[rt]=max(mx[rt],val);if(l==r)return;int mid=l+r>>1;
	if(pos<=mid)modify(lson,l,mid,pos,val);else modify(rson,mid+1,r,pos,val);
}
void modify(int rt,int l,int r,int pos){
	mx[rt]=0;if(l==r)return;int mid=l+r>>1;
	if(pos<=mid)modify(lson,l,mid,pos);else modify(rson,mid+1,r,pos);
}
int ask(int rt,int l,int r,int a,int b){
	if(a<=l&&r<=b)return mx[rt];int mid=l+r>>1,res=0;
	if(a<=mid)res=ask(lson,l,mid,a,b);if(b>mid)res=max(res,ask(rson,mid+1,r,a,b));return res;
}
void CDQ(int l,int r){
	if(l==r){ans=max(ans,s[l].ans+=s[l].c);return;}
	int mid=l+r>>1,i,j;CDQ(l,mid);sort(s+l,s+mid+1,cmp1);sort(s+mid+1,s+r+1,cmp1);
	for(j=l,i=mid+1;i<=r;++i){
		while(s[j].b<=s[i].b&&j<=mid)modify(1,1,n,s[j].l,s[j].ans),++j;
		s[i].ans=max(s[i].ans,ask(1,1,n,s[i].l,s[i].r));
	}
	for(i=l;i<=mid;++i)modify(1,1,n,s[i].l);
	sort(s+mid+1,s+r+1,cmp);CDQ(mid+1,r);
}
int main(){
	for(scanf("%d",&n),i=1;i<=n;++i)scanf("%d%d%d",a+i,b+i,c+i);
	for(i=1;i<n;++i)scanf("%d%d",&x,&y),ins(x,y);dfs(1);
	for(i=1;i<=n;++i)s[i].a=a[i],s[i].b=b[i],s[i].c=c[i],s[i].l=L[i],s[i].r=R[i];
	sort(s+1,s+n+1,cmp);CDQ(1,n);printf("%d\n",ans);
}