reroot.sublime-snippet

<snippet>
	<content><![CDATA[
vector<int>g[N],sz(N,0);
void dfs(int u,int v)
{
	sz[u]=1;
	for(auto i:g[u])
	{
		if(i!=v)
		{
			dfs(i,u);
			sz[u]+=sz[i];
		}
	}
}
void calc(int u,int v)
{
	sz[u]-=sz[i];
	sz[i]+=sz[u];
}
void reroot(int u,int v)
{
	for(auto i:g[u])
	{
		if(i!=v)
		{
			calc(u,i);

			reroot(i,u);

			calc(i,u);
		}
	}
}
void solve()
{
	int n;
	cin>>n;
	for(int i = 0;i<n;i++)cin>>a[i];
	for(int i = 0;i<n-1;i++)
	{
		int u,v;
		cin>>u>>v;
		u--;v--;
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs(0,-1);
	reroot(0,-1);
}
]]></content>
	<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
	<tabTrigger>_reroot</tabTrigger>
	<!-- Optional: Set a scope to limit where the snippet will trigger -->
	<!-- <scope>source.python</scope> -->
</snippet>