刚学线段树合并的萌新T了
查看原帖
刚学线段树合并的萌新T了
104380
garbage2楼主2021/2/4 11:29

RT,为什么T了,求助大佬们

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int ct;
int fa[N][22];
int x[2*N],v[2*N];
int al[N],dep[N],ans[N];
struct data{
	int u,cnt;
    friend bool operator < (data a,data b){
		return (a.cnt==b.cnt) ? a.u>b.u : a.cnt<b.cnt;
	}
	friend data operator + (data a,data b){
		return (data){a.u,a.cnt+b.cnt};
	}
};
vector<data> ve[N];
inline void add(int u,int sum)
{
	v[++ct]=sum;
	x[ct]=al[u];
	al[u]=ct;
}
struct onlinetree{
	int ct;
	int s[40*N][2];
	data v[40*N];
	inline void ih()
	{
		ct=n;
	}
	inline void ins(int p,int l,int r,data va)
	{
		if(r-l==1){
			v[p]=va+v[p];
			return ;
		}
		int mid=(l+r)/2;
		if(va.u<=mid)
			ins(s[p][0]==s[p][0] ? s[p][0] : ++ct,l,mid,va);
		else
			ins(s[p][1]==s[p][1] ? s[p][1] : ++ct,mid,r,va);
		v[p]=max(v[s[p][0]],v[s[p][1]]);
	}
	inline void mg(int p1,int p2,int l,int r)
	{
		if(r-l==1){
			v[p1]=v[p1]+v[p2];
			return ;
		}
		int mid=(l+r)/2;
		if(s[p1][0]&&s[p2][0])
			mg(s[p1][0],s[p2][0],l,mid);
		else if(s[p2][0])
			s[p1][0]=s[p2][0];
		if(s[p1][1]&&s[p2][1])
			mg(s[p1][1],s[p2][1],mid,r);
		else if(s[p2][1]);
			s[p2][1]=s[p2][1];
		v[p1]=max(v[s[p1][0]],v[s[p1][1]]);
	}
}lt;
inline int dfs1(int u)
{
	int i;
	for(i=0;fa[u][i];i++)
		fa[u][i+1]=fa[fa[u][i]][i];
	dep[u]=dep[fa[u][0]]+1;
	for(i=al[u];i;i=x[i])
		if(v[i]!=fa[u][0]){
			fa[v[i]][0]=u;
			dfs1(v[i]);
		}
}
inline int lca(int u,int v)
{
	if(dep[u]<dep[v])
		swap(u,v);
	int i,j;
	for(j=dep[u]-dep[v],i=0;j;j>>=1,i++)
		if(j&1)
			u=fa[u][i];
	if(u==v)
		return u;
	for(i=18;i>=0;i--)
		if(fa[u][i]!=fa[v][i]){
			u=fa[u][i];
			v=fa[v][i];
		}
	return fa[u][0];
}
inline void dfs2(int u)
{
	int i;
	for(i=al[u];i;i=x[i])
		if(v[i]!=fa[u][0]){
			dfs2(v[i]);
			lt.mg(u,v[i],0,1e5);
		}
	vector<data>::iterator it;
	for(it=ve[u].begin();it!=ve[u].end();it++)
		lt.ins(u,0,1e5,*it);
	ans[u]=lt.v[u].u;
}
int main()
{
	cin>>n>>m;
	lt.ih();
	int i;
    for(i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	dfs1(1);
	for(i=1;i<=m;i++){
		int u,v,va;
		cin>>u>>v>>va;
		int lc=lca(u,v);
	    ve[u].push_back((data){va,1});
		ve[v].push_back((data){va,1});
		ve[lc].push_back((data){va,-1});
		ve[fa[lc][0]].push_back((data){va,-1});
	}
	dfs2(1);
	for(i=1;i<=n;i++)
		cout<<ans[i]<<endl;
	return 0;
}
2021/2/4 11:29
加载中...