T1 很大的dp，考虑前i排选了j个的概率，然后转移有两种，对于每一个你可以选或者不选，然后就没有了。。

T2 用高贵的在线做法A掉了这题。。主席树套树蛤蛤。。就是内存有点怂，而且跑的比较慢。。（是不是考虑以后可以魔改一下出道题。。）

#include<cstdio>
#include<algorithm>
#define N 160010
#define M 1800010
#define P 30000010
#define biu1(cur) (ask1(1,tot,x1+1,x3,root1[cur])+ask1(1,tot,x2+1,x4,root1[cur]))
#define biu (biu1(ls[cur])+biu1(ls[cur1])-biu1(ls[cur2])-biu1(ls[cur3]))
using namespace std;
int n,p,q,a,b,x,y,mid,tot,root[N],na[N],ln,j,i;
int lc[P],rc[P],num[P],np,k,x1,x2,x3,x4,ans;
int ls[M],rs[M],root1[M],newp;
int v[N],ne[N],head[N],st[N],l,cs[N],cf,t;
int V[N],z[N],heed[N],zz[N],en[N],dad[16][N];
void add(int a,int b){v[++l]=b;ne[l]=head[a];head[a]=l;}
void add(int l,int r,int x,int y,int &cur,int cur1)
{
	cur=++np;num[cur]=num[cur1]+y;
	lc[cur]=lc[cur1];rc[cur]=rc[cur1];
	if(l==r)return;mid=(l+r)>>1;
	if(x>mid)add(mid+1,r,x,y,rc[cur],rc[cur1]);
	else add(l,mid,x,y,lc[cur],lc[cur1]);
}
void add(int l,int r,int t,int x,int y,int &cur,int cur1)
{
	cur=++newp;ls[cur]=ls[cur1];rs[cur]=rs[cur1];
	add(1,tot,x,y,root1[cur],root1[cur1]);
	if(l==r)return;mid=(l+r)>>1;
	if(t>mid)add(mid+1,r,t,x,y,rs[cur],rs[cur1]);
	else add(l,mid,t,x,y,ls[cur],ls[cur1]);
}
int lca(int x,int y)
{
	if(cs[x]>cs[y])swap(x,y);
	for(t=cf;t>=0;t--)if(cs[dad[t][y]]>=cs[x])
		y=dad[t][y];if(x==y)return x;
	for(t=cf;t>=0;t--)if(dad[t][y]!=dad[t][x])
		y=dad[t][y],x=dad[t][x];return dad[0][x];
}
void dfs(int x)
{
	st[x]=++tot;
	for(t=0;dad[t][dad[t][x]];t++)
		dad[t+1][x]=dad[t][dad[t][x]];
	cs[x]=cs[dad[0][x]]+1;if(t>cf)cf=t;
	for(int i=head[x];i;i=ne[i])
		if(v[i]!=dad[0][x])dad[0][v[i]]=x,dfs(v[i]);
	en[x]=++tot;
}
void make_tree(int x)
{
	root[x]=root[dad[0][x]];
	for(int i=heed[x];i;i=na[i])
	{
		add(1,ln,z[i],en[V[i]],-1,root[x],root[x]);
		add(1,ln,z[i],st[V[i]],1,root[x],root[x]);
	}for(int i=head[x];i;i=ne[i])
		if(v[i]!=dad[0][x])make_tree(v[i]);
}
int ask1(int l,int r,int L,int R,int cur)
{
	if((!cur)||(L>R))return 0;if(L<=l&&R>=r)return num[cur];
	int mid=(l+r)>>1,ans=0;
	if(L<=mid)ans+=ask1(l,mid,L,R,lc[cur]);
	if(R>mid)ans+=ask1(mid+1,r,L,R,rc[cur]);return ans;
}
int ask(int l,int r,int cur,int cur1,int cur2,int cur3,int k)
{
	if(l==r)return l;int s=biu,mid=(l+r)>>1;
	if(s<k)return ask(mid+1,r,rs[cur],rs[cur1],rs[cur2],rs[cur3],k-s);
	return ask(l,mid,ls[cur],ls[cur1],ls[cur2],ls[cur3],k);
}
int main()
{
	scanf("%d%d%d",&n,&p,&q);
	for(i=1;i<n;i++)scanf("%d%d",&a,&b),add(a,b),add(b,a);
	for(i=1;i<=p;i++)
	{
		scanf("%d%d%d",&a,&b,&z[i]);if(a>b)swap(a,b);
		V[i]=b;na[i]=heed[a];heed[a]=i;zz[i]=z[i];
	}sort(zz+1,zz+p+1);ln=unique(zz+1,zz+p+1)-zz-1;
	for(i=1;i<=p;i++)z[i]=lower_bound(zz+1,zz+ln+1,z[i])-zz;
	dfs(1);make_tree(1);
	for(i=1;i<=q;i++)
	{
		scanf("%d%d%d",&a,&b,&k);x=lca(a,b);
		x1=st[x];x2=st[dad[0][x]];x3=st[a];x4=st[b];
		ans=ask(1,ln,root[a],root[b],root[x],root[dad[0][x]],k);
		printf("%d\n",zz[ans]);
	}
}

T3 写了个set水过。。蛤蛤。。就是倒着做最小字典序。。挺神的。。想了不少时间没想到。。看题解的。。

day2 三题由于懒得写就不写了。。嘴巴AC