杭二联考8.23
首先我必须吐槽
上面并没什么，然而三题全连号发现了吗？原因竟然是是
所以今天就没设密码管他的。
T1
我考试按照边来考虑，想了很久。其实这题按点考虑，最后再考虑边，就很好码了。
首先计算出每个点被烧到的时间。方法：- DFS。（%%%YYB）
- 我用的树形DP（其实也不算？）先自下往上算出时间，然后自上往下更新。即：第一遍\(f[father] <- f[son] + len\) 第二遍：\(f[son] <- min(f[son],f[father]+len)\) 为什么对呢？因为烧的话只会深度先减后增（或者不增）
然后枚举边算出烧完的时间更新答案。
// It is made by XZZ#include#include #include #define Fname "firelead"using namespace std;#define rep(a,b,c) for(rg int a=b;a<=c;a++)#define drep(a,b,c) for(rg int a=b;a>=c;a--)#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])#define il inline#define rg register#define vd voidtypedef long long ll;il int gi(){ rg int x=0,f=1;rg char ch=getchar(); while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*f;}const int maxn=1e5+10,maxm=maxn<<1;int e[maxn],f[maxn],fir[maxn],nxt[maxm],w[maxm],dis[maxm],id=1,n;il vd add(int a,int b,int c){nxt[++id]=fir[a],fir[a]=id,w[id]=c,dis[id]=b;}int d[maxn],ans=0;il vd dfs(int now,int fa=-1){ if(d[now]==1){f[now]=0;return;} f[now]=2e9; erep(i,now)if(dis[i]^fa){ e[dis[i]]=i,dfs(dis[i],now); f[now]=min(f[now],f[dis[i]]+w[i]); }}il vd son(int now,int fa=-1){ erep(i,now)if(dis[i]^fa)f[dis[i]]=min(f[dis[i]],f[now]+w[i]),son(dis[i],now);}int main(){ freopen(Fname".in","r",stdin); freopen(Fname".out","w",stdout); n=gi()+1;int a,b,c; if(n==2){ a=gi(),b=gi(),c=gi(); printf("%.1f\n",c/2.00); return 0; } rep(i,2,n)a=gi(),b=gi(),c=gi()<<1,++d[a],++d[b],add(a,b,c),add(b,a,c); int root=1; drep(i,n,1)if(d[i]>1)root=i; e[root]=0; dfs(root); son(root); rep(i,1,n)if(i!=root){ int u=i,v=dis[e[i]^1],len=w[e[i]]; a=f[u],b=f[v]; if(a>b)swap(a,b); ans=max(ans,b+((len+a-b)>>1)); } printf("%.1f\n",ans/2.00); return 0;}
T2
正解？以前学长好像讲过。这里只说\(O(n^2)\)算法。
三个点在树上，肯定有且只有一个点，在它们互相之间的路径上，且和这三个点距离都相等。于是先枚举这个中间点 再进行深搜，那么答案就是\[ \sum_{d为中间点}\sum_{i=1}^{s-2}\sum_{j=i+1}^{s-1}\sum_{k=j+1}^{s}\sum_{dep=1}^{\infty}sum[i][dep]sum[j][dep]sum[k][dep] \] 上面 s表示d的儿子个数 sum[a][b]表示子树a中深度为b的点数。 dep表示你枚举的深度。 dep肯定有枚举限制的，但不好说明于是写个无限。。。 这样会过不去 加一个前缀和优化就能过 记\[ q[a][b]=\sum_{i=1}^{a}s[i][b] \] 于是不用枚举i了// It is made by XZZ#include#include #include #define Fname "hopetree"using namespace std;#define rep(a,b,c) for(rg int a=b;a<=c;a++)#define drep(a,b,c) for(rg int a=b;a>=c;a--)#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])#define il inline#define rg register#define vd voidtypedef long long ll;il int gi(){ rg int x=0,f=1;rg char ch=getchar(); while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*f;}const int maxn=5010,maxm=maxn<<1;int n,fir[maxn],nxt[maxm],dis[maxm],id;il vd add(int a,int b){nxt[++id]=fir[a],fir[a]=id,dis[id]=b;}int ans=0;int s[maxn][maxn],q[maxn][maxn],d[maxn];il vd dfs(int now,int kkk,int dep,int fa=-1){ ++s[kkk][dep]; d[kkk]=max(d[kkk],dep); erep(i,now)if(dis[i]^fa)dfs(dis[i],kkk,dep+1,now);}int main(){ // freopen(Fname".in","r",stdin); // freopen(Fname".out","w",stdout); n=gi(); int u,v; rep(i,2,n)u=gi(),v=gi(),add(u,v),add(v,u); rep(i,1,n){ int Id=0; erep(j,i){ ++Id; rep(k,1,n)s[Id][k]=0; d[Id]=0,dfs(dis[j],Id,1,i); } rep(j,1,Id)rep(k,1,n)q[j][k]=q[j-1][k]+s[j][k]; rep(b,2,Id)rep(c,b+1,Id)drep(j,min(d[b],d[c]),1) ans=(ans+q[b-1][j]*s[b][j]*s[c][j])%338; } printf("%d %d\n",ans%338+1,(ans+233)%338+1); return 0;}