1018

T1水题，开始把j敲成了i，还好后来补发了大样例。

T2
大 M 定义：对于一个序列 v[1..n]，当1<= x < y <=n 且 x,y 均为整数时，同样满足|v[x]-v[y] |<=K*|x-y|，则称 K 的最小整数值为序列 v 的 Lipschitz 常数。
现在给你一个长度为 n 的序列 v[1..n]并给出 q 个询问，对于每对询问[l,r]，你需要求出 v[l..r] 的所有子序列 v[x..y]（l<= x< y<= r）的 Lipschitz 常数之和。

骗分都挂了,MLE!!!!!!!!!!!!!!!!!!!，n<=100000,q<=100。

T3
大 M 是一只怪兽，准备到比特王国吃人。比特王国有 n 个城市，城市之间由 n1
条无向的路径连接，通过每条路径的时间为 1。其中有 m 个特别的城市，这 m 个
城市里都各有一个大神，于是大 M 打算不管普通人，只吃掉这些大神。然而大 M 是
一只具有特别能力的怪物，它可以一开始降临到 n 个城市中的任意一个城市，同时还
有一次机会在任意两个城市间打开一个虫洞，不消耗时间就能相互到达。
大 M 想知道它最少要花多少时间来吃掉这些大神（吃的时间忽略不计），如
果你不帮它它就会吃了你。
当然，大 M 是不属于这个时空的存在，所以在他吃完所有大神之后需要回到
最初降临的城市，通过时空门返回原来的位面。
m<=n<=123456

第二问对了，第一问挂了。后来TOM告诉我两者没有关系，那个点只有在虚树（大神树）上就可以了。第二问就是先dp，再找大神树的直径作为虫洞。

void dfs1(int u,int fa){
    for(int i=head[u];i!=-1;i=e[i].nxt){
        int v=e[i].v;
        if(v!=fa){
            dfs1(v,u);
            if(in[v]){
                dp[u]+=dp[v]+2;
                in[u]+=in[v];
            }
        }
    }
}
void bfs(int s,int flg){
    memset(vis,0,sizeof(vis));
    q[++hd]=make_pair(s,0);
    while(hd>=tl){
        int u=q[hd].first;int d=q[hd].second;
        hd--;
        for(int i=head[u];i!=-1;i=e[i].nxt){
            if(!vis[e[i].v]){
                if(in[e[i].v]&&d+1>ans) {
                    ans=d+1;
                    pos=e[i].v;
                }
                vis[e[i].v]=1;
                q[++hd]=make_pair(e[i].v,d+1);
            }
        }
    }
}
struct node{
    int idx;
    char s[20];
    int len;
    bool operator < (const node &x) const{
        int l=min(len,x.len);
        for(int i=1;i<=l;++i)
            if(s[i]!=x.s[i]) return s[i]<x.s[i]; 
        return len<x.len;
    }
}d[N];
int a,b;
char ss[20];
int main(){
    freopen("superm.in","r",stdin);
    freopen("superm.out","w",stdout);
    memset(head,-1,sizeof(head));
    n=read();m=read();
    for(int i=1;i<n;++i){
        a=read();b=read();
        adde(a,b);adde(b,a);
    }
    for(int i=1;i<=m;++i){
        a=read();
        in[a]++;
    }
    if(m==1) {printf("%d\n%d\n",a,0);return 0;}
    dfs1(a,0);
    bfs(a,0);
    ans=0;bfs(pos,1);
    for(int i=1;i<=n;++i){
        if(in[i]){
            d[++cnt].idx=i;
            int t=i,j=0;
            while(t){
                ss[++j]=t%10+'0';
                t/=10;
            }
            for(int jj=j;jj>=1;--jj)    d[cnt].s[jj]=ss[j-jj+1];
            d[cnt].len=j;
        }
    }
    sort(d+1,d+cnt+1);
    printf("%d\n%lld\n",d[1].idx,dp[a]-ans);
    return 0;
}