Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心，构造，线段树，树的子树

//ECR 67 A
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int T,n,s,t;
	scanf("%d",&T);
	while(T--){
		scanf("%d %d %d",&n,&s,&t);
		printf("%d\n",n-min(s,t)+1);//小的先填充n，还需n - min(s,t)填充开始出现重复 
	} 
	return 0;
}

//B
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 200005;
int id[26][maxn];
char s[maxn];
int a[26];
int main()
{
	int n,m;
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++){
		id[s[i]-'a'][++id[s[i]-'a'][0]]=i;//存每个字母第i个下标位置 
	}
	scanf("%d",&m);
	int ans = 0;
	for(int i=0;i<m;i++){
		scanf("%s",s); ans = 0; memset(a,0,sizeof(a));
		int sz = strlen(s);
		for(int j=0;j<sz;j++)
		{
			a[s[j]-'a']++; ans = max(id[s[j]-'a'][a[s[j]-'a']],ans);
			//遍历取最大值	
		}
		printf("%d\n",ans);
	}
	
	
	return 0;
}

//C
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int n,m;
struct N{int t,l,r;}q[1001];
int a[1001],vis[1001];
int main()
{
	int l,r,fg=0;
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&q[i].t,&q[i].l,&q[i].r);
	}	
	for(int i=0;i<m;i++){
		if(q[i].t==1){
			l = q[i].l,r = q[i].r;
			for(int j =l;j<r;j++)
				vis[j] = 1;
		}
	}
	int now = 1001;
	a[1]=now;
	for(int i=2;i<=n;i++){
		if(vis[i-1]==0)now--;
		a[i] = now;
	}
	for(int i=0;i<m;i++){
		l = q[i].l;r = q[i].r;
		int pos = 1;
		for(int j=l;j<r;j++){
			if(a[j]>a[j+1]){
				pos = 0; break;
			}
		}
		if(pos!=q[i].t){
			printf("NO\n");
			return 0;
		}
	}
	printf("YES\n");
	for(int i=1;i<=n;i++){
		printf("%d%c",a[i]," \n"[i==n]);
	}
	
	return 0;
}

//D
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 3e5+5;
const int inf = maxn;
struct N{
	int l,r;
	ll pre,add;
}node[maxn<<2];
queue<int> id[maxn];
int a[maxn],b[maxn];
void build(int p,int l,int r){
	node[p].l = l,node[p].r = r,node[p].add = 0;
	if(l==r){
		node[p].pre = a[l];
		return ;
	}
	int mid = (l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	node[p].pre = min(node[p<<1].pre,node[p<<1|1].pre);
}
int query(int p,int l,int r){//求最小值 
	if(node[p].l>=l&&node[p].r<=r){
		return node[p].pre;
	}
	int ans=inf;
	int mid = (node[p].l + node[p].r)>>1;
	if(l<=mid)ans = min(query(p<<1,l,r),ans);
	if(r>mid) ans = min(query(p<<1|1,l,r),ans);
	return ans;
}
void change(int p,int l,int r,int pos)//去掉 pos 点  
{
	if(l==r){
		node[p].pre = inf;
		return ;
	}
	int mid = (node[p].l + node[p].r)>>1;
	if(pos<=mid)change(p<<1,l,mid,pos);
	if(pos>mid)change(p<<1|1,mid+1,r,pos);
	node[p].pre = min(node[p<<1].pre,node[p<<1|1].pre);
}
int main()
{
	int T,n,fg = 0; scanf("%d",&T);
	while(T--){
		scanf("%d",&n); 
		fg = 0;
		for(int i=1;i<=n;i++){
			while(id[i].size())id[i].pop();
		}
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			id[a[i]].push(i);
		}
		build(1,1,n);
		for(int i=1;i<=n;i++){
			scanf("%d",&b[i]);
			if(id[b[i]].empty())fg = 1;
			if(fg)continue;
			int  nid = id[b[i]].front();
			id[b[i]].pop();
			int num = query(1,1,nid);
			if(b[i]>num){
				fg = 1;
			}else{
				change(1,1,n,nid);
			}
		}
		if(fg)printf("NO\n");
		else printf("YES\n");
	}
	
	return 0;
 } 

//E
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 200005;
struct N{
	int v,nxt;
}edge[maxn*4];
int head[maxn*4],cnt,n;
ll t[maxn],ans;
void add(int u,int v)
{
	++cnt;
	edge[cnt].v = v;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}
void dfs(int u,int f)
{
	t[u] = 1;
	for(int i = head[u];i;i=edge[i].nxt){
		int v = edge[i].v;
		if(v==f)continue;
		dfs(v,u);
		t[u]+=t[v]; 
	}
	ans+=t[u];
}
void dfs1(int u,int f,ll val)
{
	for(int i = head[u];i;i=edge[i].nxt){
		int v = edge[i].v;
		if(v==f)continue;
		ll temp = val - t[v] + n - t[v];
		ans = max(ans,temp);
		dfs1(v,u,temp);
	}
}
int main()
{
	int u,v;
	scanf("%d",&n);
	for(int i=0;i<n-1;i++)
	{
		scanf("%d %d",&u,&v);
		add(u,v);
		add(v,u);
	} 
	dfs(1,0);
	dfs1(1,0,ans);
	cout<<ans<<endl;
	return 0;
}