1、给定一个数字$N$，从1到100的100个数字中选出$K$个数字（设为集合$S$），然后对$S$进行如下运算：

（1）删除$S$中的某些数字；（可以删除0个数字）

（2）将$S$中的某些数字取为它的相反数；（可以改变0个数字）

（3）对$S$中的数字求和得到$ans$

现在给出一种选择$K$个数的方法使得无论如何操作，$ans \neq N$。$1\leq N \leq 100,1\leq K \leq 15$

思路：从2开始枚举选择一个数字$x$，使得$N$%$x\neq 0$，然后选择$x,2x,3x,...,Kx$。这样的话无论如何操作最后的$ans$都是$x$ 的倍数。但是当$N=60$时$x=7$，这是如果$K=15$，最后会选择105,这是可以特殊处理，把105换成1.因为7的任何倍数加减1都不会是60.

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;class WolfCardGame{public: vector
            
              createAnswer(int n,int K) { vector
             
               ans; for(int i=2;;++i) if(n%i) { for(int j=1;j<=K;++j) ans.push_back(i*j); if(i==7) { ans[K-1]=1; } break; } return ans; }};
             
            
           
          
         
        
       
      
     

 

2、对于一个有向树（树边是有方向的）$T$，定义$f(T)$表示这样的顶点对的个数:$(u,v)$，存在从$u$到$v$的路径。现在给定一棵$n$个顶点的无向树，给每条边选择一个方向，那么有$2^{n-1}$种方式，计算每种方式产生的有向树的$f$值之和。

思路：考虑树分治。对于现在的树的重心$S$，那么对答案有贡献的顶点对有两种：要么顶点对其中的一个顶点是$S$，要么是跨过$S$的两个顶点。第一种容易计算，因为设另一个顶点是$u$，那么$u$与$S$之间的边的方向是相同的，而其他的边的方向任意，所以设它们之间的边的个数是$x$，那么对答案的贡献是$g(u)=2*2^{n-1-x}=2^{n-x}$。对于第二种，当前遍历的顶点$v$与之前遍历的顶点$u$之间的边方向是相同的，其余的边方向任意。所以设之前遍历的所有的$S$的子树得到的所有的节点的$g$值之和为$K$，$v$和$S$之间边的个数是$y$，那么当前节点的贡献为$h(v)=\frac{K}{2^{y}}$.

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;const int N=100005;const int mod=1000000007;vector
            
              g[N];int n;int a[N];int d[N];int fa[N];int p[N];int Pow(int a,int b){ int ans=1; while(b) { if(b&1) ans=(long long)ans*a%mod; a=(long long)a*a%mod; b>>=1; } return ans;}const int base=Pow(2,mod-2);void init(){ p[0]=1; for(int i=1;i
             
              MaxSon[u]) MaxSon[u]=Son[v]; } }}int getcenter(int u){ aNum=0; DFS(u,-1); int ans=u,Min=aNum; for(int i=1;i<=aNum;++i) { int v=a[i]; int tmp=max(aNum-MaxSon[v],MaxSon[v]); if(tmp