求助!60pts
  • 板块P4178 Tree
  • 楼主DeNeRATe
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/9/6 20:11
  • 上次更新2023/11/5 13:36:20
查看原帖
求助!60pts
38171
DeNeRATe楼主2020/9/6 20:11
//P4178
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define LL long long
#define Lowbit(X) (X&(-X))
#define Lson Child[X][0]
#define Rson Child[X][1]
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define FOR_SIDE(i,A) for(LL i=Head[A];i;i=Next[i])
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const LL MAXN=4e4+10,Top=100000000;

LL Total,u,v,w,Dep[MAXN]={0,1},Ans[MAXN],Y;
LL Next[MAXN<<1],Head[MAXN],End[MAXN<<1],Cur,Val[MAXN<<1];
LL Limit,Dfn[MAXN],Dot[MAXN],dfn_num,Son[MAXN],Size[MAXN];
LL Sum[MAXN<<5],Child[MAXN<<5][2];

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

LL ID[MAXN<<5],Root,P;

inline void Push_up(LL X) { Sum[X]=Sum[Lson]+Sum[Rson]; }
inline void Update(LL &X,LL L,LL R,LL Loc,LL Val) {
	if(!X) { X=ID[P--]; Child[X][0]=Child[X][1]=Sum[X]=0; }
	if(L==R) {
		Sum[X]+=Val;
		return;
	}
	LL Mid=(L+R)>>1;
	if(Loc<=Mid) Update(Lson,L,Mid,Loc,Val);
	else Update(Rson,Mid+1,R,Loc,Val);
	Push_up(X); 
}
 
inline LL Get(LL &X,LL L,LL R,LL From,LL To) {
	if(!X) { return 0; }
	if(L>=From && R<=To) return Sum[X];
	LL Mid=(L+R)>>1,Res=0;
	if(From<=Mid) Res+=Get(Lson,L,Mid,From,To);
	if(To>Mid) Res+=Get(Rson,Mid+1,R,From,To);
	Push_up(X);
	return Res;
} 

inline void DFS_one(LL New,LL Pre) {
    Dfn[New]=++dfn_num;
    Dot[dfn_num]=New;
    Size[New]=1;
    LL Res=0;
    FOR_SIDE(i,New) {
        if(End[i]==Pre) continue;
        Dep[End[i]]=Dep[New]+Val[i];
        DFS_one(End[i],New);
        Size[New]+=Size[End[i]];
        if(Size[End[i]]>Res) Res=Size[End[i]],Son[New]=End[i];
    }
}

inline void Delete(LL &X,LL L,LL R) {
    if(!X) return;
    LL Mid=(L+R)>>1;
    Delete(Lson,L,Mid);
    Delete(Rson,Mid+1,R);
    ID[++P]=X;
    Sum[X]=0;
    X=0;
    Push_up(X);
}

inline void DFS_two(LL New,LL Pre,bool Keep) {
    FOR_SIDE(i,New) {
        if(End[i]==Pre || End[i]==Son[New]) continue;
        DFS_two(End[i],New,false);
        Ans[New]+=Ans[End[i]];
    }
    if(Son[New]) { DFS_two(Son[New],New,true); Ans[New]+=Ans[Son[New]]; }
    Ans[New]+=Get(Root,1,Top,1,Limit+Dep[New]);
    Update(Root,1,Top,Dep[New],1);
    FOR_SIDE(i,New) {
    	if(End[i]==Pre || End[i]==Son[New]) continue;
    	FOR(j,Dfn[End[i]],Dfn[End[i]]+Size[End[i]]-1)
            Ans[New]+=Get(Root,1,Top,1,Limit+2*Dep[New]-Dep[Dot[j]]);
        FOR(j,Dfn[End[i]],Dfn[End[i]]+Size[End[i]]-1)
    	    Update(Root,1,Top,Dep[Dot[j]],1);
    }
    if(!Keep) Delete(Root,1,Top);
}

inline void Add_Edge(LL From,LL To,LL Temp) {
	Next[++Cur]=Head[From];
	Head[From]=Cur;
	End[Cur]=To;
	Val[Cur]=Temp;
}

inline LL Read() {
    LL Fac=1,Temp=0;
    char Ch=getchar();
    while(Ch>'9' || Ch<'0') {
        if(Ch=='-') Fac=-1;
        Ch=getchar();
    }
    while(Ch>='0' && Ch<='9') {
        Temp=(Temp<<1)+(Temp<<3)+Ch-'0';
        Ch=getchar();
    }
    return Fac*Temp;
}

int main() {
    //File();
    FOR(i,1,(MAXN<<5)-5) ID[++P]=i;
    Total=Read();
    FOR(i,1,Total-1) {
        u=Read(); v=Read(); w=Read();
        Add_Edge(u,v,w); 
        Add_Edge(v,u,w);
    }
    Limit=Read();
    DFS_one(1,0);
    DFS_two(1,0,0);
    printf("%lld\n",Ans[1]);
    //fclose(stdin); fclose(stdout);
    system("pause");
    return 0;
}
2020/9/6 20:11
加载中...