题目：
先写了暴力分的44分。那个两棵树、其中一棵是编号连续的链、边权都是1的点好像可以线段树合并，但没写。
#include#include #include #define ll long longusing namespace std;ll rdn(){ ll ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret;}ll Mx(ll a,ll b){ return a>b?a:b;}const int N=1e5+5,M=3005,K=20;int n,hd[3][N],xnt,to[3][N<<1],nxt[3][N<<1];ll w[3][N<<1],dis[N],ans,ds2[M][M]; bool flag;void add(int t,int x,int y,ll z){to[t][++xnt]=y;nxt[t][xnt]=hd[t][x];hd[t][x]=xnt;w[t][xnt]=z;}void chk(int cr,int fa){ for(int i=hd[0][cr],v;i;i=nxt[0][i]) if((v=to[0][i])!=fa) { bool fg=0;ll tw; for(int j=hd[1][cr];j;j=nxt[1][j]) if(to[1][j]==v){fg=1;tw=w[1][j];break;} if(!fg||tw!=w[0][i]){flag=1;return;} for(int j=hd[2][cr];j;j=nxt[2][j]) if(to[2][j]==v){fg=1;tw=w[2][j];break;} if(!fg||tw!=w[0][i]){flag=1;return;} chk(v,cr);if(flag)return; }}void dfs1(int cr,int fa){ ll mx=0,mx2=0; for(int i=hd[0][cr],v;i;i=nxt[0][i]) if((v=to[0][i])!=fa) { dfs1(v,cr);ll tp=dis[v]+w[0][i]; if(tp>mx)mx2=mx,mx=tp; else if(tp>mx2)mx2=tp; } ans=Mx(ans,mx+mx2);dis[cr]=mx;}void dfs2(int cr,int fa,ll lj,int t,int rt){ ds2[rt][cr]+=lj; for(int i=hd[t][cr],v;i;i=nxt[t][i]) if((v=to[t][i])!=fa)dfs2(v,cr,lj+w[t][i],t,rt);}void solve2(){ for(int t=0;t<3;t++) for(int i=1;i<=n;i++)dfs2(i,0,0,t,i); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)ans=Mx(ans,ds2[i][j]); printf("%lld\n",ans);}int main(){ n=rdn(); for(int t=0;t<3;t++) { ll z;xnt=0; for(int i=1,u,v;i
正解要边分治和虚树，现在还不会。所以用了随机化。
卡时间可以调用 clock() ，返回的是 CPU 周期，CLOCKS_PER_SEC 返回的是一秒运行了几个 CPU 周期，所以 clock() / CLOCKS_PER_SEC 可以算出运行了几秒。
随机一个根，暴力算每个点到这个根的距离（3个距离求和），把距离当前根最远的那个点设为新的根，同时更新答案。做几次之后就再随机一个根。这个间隙可以小一些，10或者8之类的。
可以打 vis[ ] 标记，作过根的点就不再作根了。
还是通不过 UOJ 的 hack 数据。
#include#include #include #include #define ll long long#define db doubleusing namespace std;ll rdn(){ ll ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret;}ll Mx(ll a,ll b){ return a>b?a:b;}const int N=1e5+5,TL=3850;int n,hd[3][N],xnt,to[3][N<<1],nxt[3][N<<1];ll w[3][N<<1],dis[N],ds1[3005][3005],ans;bool vis[N];void add(int t,int x,int y,ll z){to[t][++xnt]=y;nxt[t][xnt]=hd[t][x];hd[t][x]=xnt;w[t][xnt]=z;}int clk(){ return (db)clock()/CLOCKS_PER_SEC*1000;}//msvoid dfs1(int cr,int fa,ll lj,int t,int rt){ ds1[rt][cr]+=lj; for(int i=hd[t][cr],v;i;i=nxt[t][i]) if((v=to[t][i])!=fa)dfs1(v,cr,lj+w[t][i],t,rt);}void solve1(){ for(int t=0;t<3;t++) for(int i=1;i<=n;i++)dfs1(i,0,0,t,i); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)ans=Mx(ans,ds1[i][j]); printf("%lld\n",ans);}void dfs(int cr,int fa,ll lj,int t){ dis[cr]+=lj; for(int i=hd[t][cr],v;i;i=nxt[t][i]) if((v=to[t][i])!=fa)dfs(v,cr,lj+w[t][i],t);}int cz(int rt){ for(int i=1;i<=n;i++)dis[i]=0; for(int t=0;t<3;t++)dfs(rt,0,0,t); int ret=0; for(int i=1;i<=n;i++) { if(dis[i]>ans)ans=dis[i]; if(!vis[i]&&dis[i]>dis[ret])ret=i; } return ret;}int main(){ n=rdn();ll z; for(int t=0;t<3;t++,xnt=0) for(int i=1,u,v;i