第一题：
个人做的第4个网络流题，很幸运的A了
这是比较直观的网络流建模题了：
#include<iostream> #include<cstdio> using namespace std; #include<cstring> #include<queue> #define inf 1e6 #define N 4000 #define M 1000001 queue<int>q; short ya[1001]; short tu[1001][1601]; int xia[N],yuan[N],hou[M],zhong[M],zhi[M],tot=-1,dis[N],i,n,m,s,t; char uu; int x,y; void jia(int x,int y,int z) { hou[++tot]=yuan[x],yuan[x]=tot,zhi[tot]=z,zhong[tot]=y; } void jian(int x,int y,int z) { jia(x,y,z); jia(y,x,0); } bool bfs(int s,int t) { memset(dis,0x7f,sizeof(dis)); for(i=1;i<=t+1;i++) { xia[i]=yuan[i]; } q.push(s); dis[s]=1; while(!q.empty()) { int st=q.front(); q.pop(); for(i=xia[st];i!=-1;i=hou[i]) { int nd=zhong[i]; // cout<<st<<" "<<nd<<endl; if(dis[nd]>inf&&zhi[i]) { dis[nd]=dis[st]+1; q.push(nd); } } } return dis[t]<inf; } int dfs(int now,int t,int limit) { if(now==t||!limit)return limit; int i,flow=0,f; for(i=xia[now];i!=-1;i=hou[i]) { xia[now]=i; int nd=zhong[i]; if(dis[nd]==dis[now]+1&&(f=dfs(nd,t,min(zhi[i],limit)))) { flow+=f; limit-=f; zhi[i]-=f; zhi[i^1]+=f; if(!limit)break; } } return flow; } int dinic(int s,int t) { int daan=0; while(bfs(s,t)) {//cout<<dis[4]<<" "<<dis[5]<<endl; //cout<<endl<<endl; daan+=dfs(s,t,inf); // cout<<daan<<endl; } return daan; } void zhaowzh(int now) { jian(2*n+now,n+now,1); for(int i=1;i<=tu[now][0];i++) { if(ya[tu[now][i]]==0||ya[tu[now][i]]==1)jian(2*n+now,n+tu[now][i],1); } } void jiantu(int now) { if(ya[now]==2)jian(now,t,1); else for(int i=1;i<=tu[now][0];i++) { if(ya[tu[now][i]]==2) { jian(now,tu[now][i],1); } } } int main() { memset(yuan,-1,sizeof(yuan)); scanf("%d%d",&n,&m); s=3*n+1; t=3*n+2; scanf("%c",&uu); for(i=1;i<=n;i++) { scanf("%c",&uu); if(uu=='E')ya[i]=0; if(uu=='J')ya[i]=1; if(uu=='T')ya[i]=2; // cout<<ya[i]<<" "; } for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); tu[x][++tu[x][0]]=y; tu[y][++tu[y][0]]=x; } for(i=1;i<=n;i++) { jian(i+n,i,1); if(ya[i]==1) { jian(s,i+2*n,1); zhaowzh(i); } jiantu(i); } printf("%d",dinic(s,t)); }
第二题：
明显的博弈，直接弃（话说手玩能有10分实在无语、）
第三题
这题是被卡的最惨的一个题了，因为这个题分析了很长时间还是没有结果。
首先想到的肯定是lca求距离，n^2 logn暴力，但会惨烈的超时；（觉得应该是点分治，因为学姐讲过）
然后尝试找线性关系，可以发现往父亲上跳，它所在的子树+=边权，父亲的其他子树-=边权；；
这可以维护一个区间加减，但单点查询+排序实在不好搞，时间上天；
然后想了一个二分权值，统计size的方法，但感觉不太稳定（很可能不如暴力）
只有nlog^2(n)级别的才能搞，但实在想不出来了（这种单点查询n^2超时的实在太毒瘤了）
个人感觉nlog(n)搞出答案不现实。
好吧，又死在正解门口了
不过要想独立做出来这个题还需要树分治（又被算法卡了）
先学一段的树分治再说、
