前言

关于\(NOIP2018\)，详见此博客：。

\(Day2\)的题目和\(Day1\)比起来，真的是难了很多啊。

\(T1\)：旅行（）

对于树的情况，显然可以把相邻的点全部存下来，排序一遍后依次遍历即可。

对于基环外向树的情况，一种简单的方法是每次断一条边，把它当成树的情况，这样是\(O(n^2)\)的。

但我考场上没想到这种做法，结果对于环上的情况单独讨论，结果把这题弄成了一个极为复杂的模拟题，总共打了两个小时才打完。不过我这样的做法貌似是\(O(n)\)的（如果不算\(sort\)的\(log\)）。

具体是怎么做的就不讲了（比较麻烦），有兴趣可以看一下代码（要看的话最好画图理解一下）。

我个人还是比较推荐用删边的做法的。

\(P.S.\)貌似有一个加强版的题目：，我这种做法是能过的。

代码如下：

#include
    
     #define N 5000#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)#define swap(x,y) (x^=y^=x^=y)using namespace std;int n,m,ee,cur,lnk[N+5],vis[N+5],data[N+5]; struct edge{    int to,nxt;}e[(N<<1)+5];class Class_TreeSolver//对于树的情况{    public:        inline void Solve(int x=1,int lst=0)        {            register int i,H=cur+1,T;            for(printf("%d ",x),i=lnk[x];i;i=e[i].nxt) e[i].to^lst&&(data[++cur]=e[i].to);            for(T=cur,sort(data+H,data+T+1),i=H;i<=T;++i) Solve(data[i],x);        }}TreeSolver;inline void Begin_Circle(int,int);class Class_CircleTreeSolver//对于基环外向树的情况{    private:        int Top,used[N+5],StackH[N+5],StackT[N+5],StackPos[N+5];        class Class_CircleChecker//判断一个节点是否在环中        {            private:                int Found,fa[N+5],In[N+5],vis[N+5],Depth[N+5];            public:                Class_CircleChecker() {Found=0;}                inline void Init(int x=1,int lst=0)//初始化                {                    register int i,y;                    for(vis[x]=1,i=lnk[x];i;i=e[i].nxt)                    {                        if(!(e[i].to^lst)) continue;                        if(vis[y=e[i].to])                         {                            if(Depth[x]
     
      Depth[y]) In[x]=1,x=fa[x];                            while(x^y) In[x]=In[y]=1,x=fa[x],y=fa[y];                            return (void)(In[x]=Found=1);                        }                        if(Depth[e[i].to]=Depth[fa[e[i].to]=x]+1,Init(e[i].to,x),Found) return;                    }                    vis[x]=0;                }                inline bool InCircle(int x) {return In[x];}//判断x是否在环中        }C;        inline void dfs(int x,int lst)//普通的dfs        {            if(used[x]) return;            if(C.InCircle(x)) return Begin_Circle(x,lst);//如果当前节点在环上，特殊处理            register int i,H=cur+1,T;            for(used[x]=1,printf("%d ",x),i=lnk[x];i;i=e[i].nxt) !used[e[i].to]&&(data[++cur]=e[i].to);            for(T=cur,sort(data+H,data+T+1),i=H;i<=T;++i) dfs(data[i],x);        }        inline void dfs_Circle(int x,int lst,int Begin,int OtherSide)//在环上dfs        {            if(used[x]) return;//如果访问过当前节点，退出            register int i,H=cur+1,T;            for(used[x]=1,printf("%d ",x),i=lnk[x];i;i=e[i].nxt) !used[e[i].to]&&(data[++cur]=e[i].to);            for(T=cur,sort(data+H,data+T+1),i=H;i
      
       1)//如果栈中元素个数大于1                     {                        for(i=StackH[Top];i<=StackT[Top];++i) dfs(data[i],StackPos[Top]);//处理当前栈顶元素可到达的剩余节点                        --Top;//弹出                    }                    while(StackH[1]<=StackT[1]&&data[StackH[1]]
      
     
    

\(T2\)：填数游戏（）

如果用\(ans_{x,y}\)表示\(n=x,m=y\)时的答案，则我们要知道两个性质：

1. 对于任意\(n,m\)，满足\(ans_{n,m}=ans_{m,n}\)。（显然）
2. 对于任意\(m>n+1\)，满足\(ans_{n,m}=ans_{n,n+1}*3^{m-n-1}\)。（我也不会证）

则不难发现，我们只需求出\(ans_{i,i}\)和\(ans_{i,i+1}(1\le i\le8)\)，就可以推出全部答案。

据说\(ans_{i,i}\)与\(ans_{i-1,i-1}\)、\(ans_{i,i+1}\)与\(ans_{i,i}\)之间是有一定数量关系的，然而我并没有找到规律。

但是没关系，我们还可以打表啊！

不难发现，对于每一条从左下向右上的斜线中，必然可以被分成两部分，其中前一部分全为\(0\)，后一部分全为\(1\)（或整条线全为\(0\)或\(1\)）。

那么，我们就可以枚举每条斜线中选择多少个\(1\)，然后对其进行\(O(nm(n+m))\)验证，就可以在较快的时间内打完表了（实际上我打了一个下午）。

代码如下：

#include
    
     #define MOD 1000000007#define N 8#define swap(x,y) (x^=y^=x^=y)#define GetID(x,y) ((x)-2<<1|(y))using namespace std;const int List[2*N]={12,36,112,336,912,2688,7136,21312,56768,170112,453504,1360128,3626752,10879488};//最后打出来的表（我将二维压成了一维）int n,m;class Class_ListMaker//打表代码{    private:        #define ListSize 8        int n,m,ans,num[N+5][N+5];        inline bool IsLegal(int x,int y)//验证当前位置合法性        {            register int x1=x,y1=y+1,x2=x+1,y2=y;            while(x1+y1<=n+m)             {                if(num[x1][y1]^num[x2][y2]) return num[x1][y1]
     
      n+m) return (void)(!((ans+=check())^MOD)&&(ans=0));            for(Solve(s+1),i=n;i;--i) s-i>=1&&s-i<=m&&(num[i][s-i]=1,Solve(s+1),0);            for(i=n;i;--i) s-i>=1&&s-i<=m&&(num[i][s-i]=0);        }    public:        inline void MakeList()         {            freopen("List.txt","w",stdout);            for(cout<<"const int List[2*N]={",n=2;n<=ListSize;++n) m=n,ans=0,Solve(),printf("%d,",ans),m=n+1,ans=0,Solve(),printf("%d%c",ans,n^ListSize?',':'}');//输出表            putchar(';'),exit(0);        }}M;inline int quick_pow(int x,int y){    register int res=1;    while(y) (y&1)&&(res=1LL*res*x%MOD),x=1LL*x*x%MOD,y>>=1;    return res;}int main(){//  M.MakeList();    freopen("game.in","r",stdin),freopen("game.out","w",stdout);    scanf("%d%d",&n,&m),n>m&&swap(n,m),printf("%d",n^1?(m<=n+1?List[GetID(n,m-n)]:1LL*List[GetID(n,1)]*quick_pow(3,m-n-1)%MOD):quick_pow(2,m));//依据规律输出答案    return 0;}
     
    

\(T3\)：保卫王国（）

这题的正解是动态DP，不会动态DP的可以先去做这道。

好吧，实际上这题是可以用倍增+\(DP\)来解决的。

考虑用\(In_{x,0/1}\)来表示不选/选\(x\)节点时在\(x\)子树内达成条件的最小代价（为方便起见，我们再用一个\(In_{x,2}\)来表示\(min(In_{x,0},In_{x,1})\)），并用\(Out_{x,0/1}\)来表示不选/选\(x\)节点时在\(x\)子树外达成条件的最小代价。

这两个数组可以通过两遍\(dfs\)来预处理。

然后，我们还要预处理出一个数组\(f_{x,y,sx(0/1),sy(0/1)}\)来表示当\(x\)不选/选，\(fa_{x,y}\)不选/选时，使属于以\(fa_{x,y}\)为根子树而不属于以\(x\)为根子树的所有节点达成条件的最小代价。

这个数组可以在预处理\(fa\)数组时一起预处理掉。

只要枚举\(fa_{i,j-1}\)选与不选就可以进行转移了。

而对于询问，我们就采用倍增\(LCA\)的思想向上跳。

如果两个节点为祖先关系，则直接向上跳，一边跳一边用一个数组\(g_{0/1}\)记录在当前节点不选与选时使当前子树满足条件分别需要的最小代价，最后答案就是\(g_{sx}+Out_{y,sy}\)。

而不为祖先关系的情况也是同理的，分别将两个节点跳到\(LCA_{x,y}\)的左右子节点，然后枚举\(LCA_{x,y}\)选与不选，然后减去之前预处理时得到的答案，加上新求出的最小代价，即可求出答案。

具体实现见代码：

#include
    
     #define N 100000#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)#define swap(x,y) (x^=y^=x^=y)#define min(x,y) ((x)<(y)?(x):(y))#define Gmin(x,y) (x>(y)&&(x=(y)))#define LL long long#define INF 1e18using namespace std;int n,ee,lnk[N+5],Cost[N+5];struct edge{    int to,nxt;}e[(N<<1)+5];class Class_FIO{    private:        #define Fsize 100000        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,Fsize,stdin),A==B)?EOF:*A++)        #define pc(ch) (void)(FoutSize